#include <cstdio>
#include <fstream>
#define nmax 1000001
using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
int p[nmax+5],st,dr,test,mijl,n,k,sol;
int16_t t[nmax+5];

int v[8][500001],maxim[8];


int main()
{int i,j;

for (i=1;i<nmax;i++) p[i]=i;
for (i=2;i<nmax;i++) if (p[i]!=1)
            {p[i]=1;
             t[i]=1;
             for(j=2*i;j<nmax;j+=i) if (p[j]%i==0)
                        {t[j]++;
                         while (p[j]%i==0) p[j]/=i;
                         }
             }
for (i=1;i<nmax;i++) {maxim[t[i]]++;
                      v[t[i]][maxim[t[i]]]=i;}
fscanf(f,"%d",&test);
for (i=1;i<=test;i++) {fscanf(f,"%d %d",&n,&k);
                       st=1;
                       dr=maxim[k];
                       sol=0;
                       while (st<=dr) {mijl=(st+dr)>>1;
                                       if (v[k][mijl]<=n) {sol=mijl;
                                                           st=mijl+1;}
                                                      else dr=mijl-1;
                                       }
                       fprintf(g,"%d\n",v[k][sol]);
                       }



return 0;
}