#include <cstdio>
#define Max 1000000
#define Max2 500000
#include <fstream>
using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
int16_t ciur[Max+1]={0};
int v[8][500000],n,k;

int cautbin(int p,int q)
{if (p>q) return 0;

int mid=(p+q)>>1;

if (v[k][mid]<=n&&v[k][mid+1]>n) return mid;

if (n>v[k][mid]) return cautbin(mid+1,q);

return cautbin(p,mid-1);

}
int main()
{int i,j,t,l;fscanf(f,"%d",&t);
for (i=2;i<=Max2;i++) if (ciur[i]==0) for (j=2*i;j<=Max;j+=i) ciur[j]++;


for (i=1;i<=Max;i++) if (ciur[i]<=7) v[ciur[i]][++v[ciur[i]][0]]=i;


for (i=1;i<=t;i++) {fscanf(f,"%d %d",&n,&k);
                    l=cautbin(1,v[k][0]);

                    if (l==0) fprintf(g,"0\n");
                    if (l>0) fprintf(g,"%d\n",v[k][l]);
                    }


return 0;
}