#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int i,j,n,k,x,nr[1000001],a[8][1000001],st,dr,mij,p,v[1000001],t;
int main()
{
v[0]=1;
    for(i=2;i<=1000001;i++){
        if(v[i]==0){
            nr[i]++;
            for(j=2*i;j<=1000001;j+=i){
                v[j]=1;
                nr[j]++;}

        }}
        for(i=1;i<=1000001;i++)

        if(nr[i]<=7)
            a[nr[i]][++a[nr[i]][0]]=i;
f>>n;
    for(t=1;t<=n;t++){
            f>>x>>k;
        st=1,dr=a[k][0],p=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(a[k][mij]>x)
                dr=mij-1;
            else
            {
                st=mij+1;
                p=a[k][mij];
            }

        }
g<<p<<'\n';

    }


    return 0;
}