#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
const int N=1000001;
bool a[N];
int div(int x){
    int nr=0;
    for(int i=2;i<=x;i++)
        if(a[i]==false && x%i==0)
            nr++;
    return nr;
}
int main()
{
    int i,pas,x,n,k,j,t,l,cod;
    f>>t;
    for(i=2;i*i<=N-1;i++)
            for(j=i*i;j<=N;j+=i)
                a[j]=true;
    for(j=1;j<=t;j++){
        f>>n>>k;
        i=n;
        pas=1<<20;
        x=0;
        cod=0;
        while(pas!=0 && cod==0){
            if(pas<=n  && cod==0){
                for(l=i;l>pas && cod==0;l--)
                    if(div(l)==k){
                        x=l;
                        cod=1;
                    }
                i=pas;
            }
            pas/=2;
        }
        g<<x<<"\n";
    }
    return 0;
}