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

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

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

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

return cautbin(p,mid-1);

}
int main()
{int i,j,t;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);

                    fprintf(g,"%d\n",v[k][cautbin(1,v[k][0])]);
                    }


return 0;
}