/*#include<fstream.h>
long a[100],T,x,nn[6];
ofstream fout("loto.out");
short n;
void citire(){
ifstream fin("loto.in");
fin>>n>>T;
for (short i=0;i<n;i++)
  fin>>a[i];
fin.close();
}
void bule(long a[]){
short ok=0,p=n;
while(ok==0){
ok=1;
p--;
for (short i=0;i<p;i++)
    if (a[i]>a[i+1]){
       long aux=a[i];
       a[i]=a[i+1];
       a[i+1]=aux;
       ok=0;}
}

for(short j=0;j<16;j++) {
   short nr0=0,nr1=0;
for(short i=0;i<n;i++)
	if((zero[i]&(1<<j))!=0)
	   unu[nr1++]=zero[i];
	else
	   zero[nr0++]=zero[i];
	nr1=0;
	for(short k=nr0;k<n;k++)
	   zero[k]=unu[nr1++];
}


}
int caut(long x){
int st=0,dr=n-1,m;
while (st<dr){
m=(st+dr)/2;
if (a[m]==x)
    return 1;
    else
    if (a[m]<x)
       st=m+1;
       else dr=m-1;}
return 0;
}
int parc(){
long S,nr=0,nr1=0,ok=1;
double ww=T/6;
if (T/6==ww) {
   for (int i=0;i<n;i++)
      if (a[i]==ww){
	 for (int tt=0;tt<6;tt++)
	    fout<<a[i]<<" ";
	 return 0;}
   }
for (int c=0;c<n;c++)
     if (a[c]*6<T)
	nr1++;
      else
	break;
for (int pp=n-1;pp>=0;pp--)
   if (a[pp]*6>T)
      nr++;
for (short i=n-nr-1;i>=nr1-1;i--)
for (short j=n-1;j>=0;j--)
for (short k=n-1;k>=0;k--)
for (short l=n-1;l>=0;l--)
for (short o=n-1;o>=0;o--)
   if (caut(T-a[i]-a[j]-a[k]-a[l]-a[o])==1){
   n=5;
   nn[0]=a[i];nn[1]=a[j]; nn[2]=a[k]; nn[3]=a[l]; nn[4]=a[o]; nn[5]=T-a[i]-a[j]-a[k]-a[l]-a[o];
   bule(nn);
   for (int qqq=0;qqq<6;qqq++)
      fout<<nn[qqq]<<" ";
   // fout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[l]<<" "<<a[o]<<" "<<T-a[i]-a[j]-a[k]-a[l]-a[o]<<"\n";
    return 1;}
return 0;
}
int main(){
citire();
bule(a);
if (parc()==0)
  fout<<"-1";
return 0;
}
*/

#include<fstream.h>
long N,K,T;
int sir(int N,int K){
for (long i=N;i>1;i--){
long x=i,nr=0;
if (x%2==0)
  nr=1;
while (x%2==0)
   x/=2;
   for (long d=3;d<=x/d;d+=2)
       if (x%d==0){
	  nr++;
      while (x%d==0)
	   x/=d;  }
   if (x!=1)
       nr++;
if (nr==K)
   return i;     }
return 0;
}
void citire(){
ifstream fin("divprim.in");
ofstream fout("divprim.out");
fin>>T;
for (long i=0;i<T;i++){
    fin>>N>>K;
    fout<<sir(N,K);
    fout<<"\n";}
fin.close();
fout.close();
}
int main(){
citire();
return 0;
}