//Gurzau Roland
//C.N.A.S.
// 10
// [email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

void ciur(int N,int p[],int v[],int &k){ p[1]=1,p[2]=0;k=2; //ciur+vect nr prime
v[1]=2;
for(int d=4;d<=N;d+=2)
    p[d]=1;

for(int d=3;d<=N;d+=2)
   if(p[d]=0){v[k]=d;k++;
    for(int i=d*d;i<=N;i+=d)
        p[i]=1;

        }

}


int main()
{
    int T,N,K,p[200000]={0},divpr,v[4000],k;
    fin>>T;

    for(int i=1;i<=T;i++)
    {
        fin>>N>>K;
        divpr=0;
      ciur(N,p,v,k);





        for(int a=N;a>1;a--)//luam nr de la n la 1
        {if(K==1&&N<2){fout<<0<<endl;break;}if(K==2&&N<6){fout<<0<<endl;break;}if(K==3&&N<30){fout<<0<<endl;break;}if(K==4&&N<210){fout<<0<<endl;break;};if(K==5&&N<2310){fout<<0<<endl;{fout<<0<<endl;break;};};if(K==6&&N<30030){fout<<0<<endl;break;};  if(K==7&&N<510510){cout<<0<<endl;break;};//impun limite pt N min
            for(int b=1;b<k;b++)
                {if(a%v[b]==0)divpr++;
                if(divpr>K)break;}

             if(divpr==K)
             {
                 fout<<a<<endl;
                 break;
             }

        }

    }


    return 0;
}