#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int i,j,t,d,nr,k,kk,st,dr,mij,elem;
short int ciur[1000004];
struct ura
{
    short int v[250000];
} vv[10];
int main()
{
    for(i=2;i*i<=1000000;i++)
    {
        if(ciur[i]==0)
        {
            for(j=i*2;j<=1000000;j+=i)
                ciur[j]++;
        }
    }
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0) ciur[i]++;
    for(d=0;d<=7;d++)
    {
       kk=0;
       for(i=1;i<=1000000;i++)
           if(ciur[i]==d) kk++,vv[d].v[kk]=i;
        vv[d].v[0]=kk;
    }
    fin>>t;
    for(d=1;d<=t;d++)
    {
        fin>>nr>>k;
        st=1;
        dr=vv[k].v[0];
        elem=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(vv[k].v[mij]==nr)
            {elem=nr;
            break;
            }
            if(vv[k].v[mij]>nr)
                dr=mij-1;
            if(vv[k].v[mij]<nr)
                st=mij+1,elem=vv[k].v[mij];
        }
        fout<<elem<<'\n';
    }
    return 0;
}