#include<fstream.h>
int a[1000001];
int d[1000001][8];
int i,j,t,x,y;
int main()
{ifstream q("divprim.in");
ofstream w("divprim.out");
q>>t;
for(i=1;i<=500000;i++)
  a[(i<<1)]=1;
for(i=3;i<=1000000;i++)
  if(!a[i])
    for(j=1;j*i<=1000000;j++)
	  a[i*j]++;
d[1][0]=1;
for(i=2;i<=1000000;i++)
  {for(j=0;j<=7;j++)
	 d[i][j]=d[i-1][j];
  d[i][a[i]]=i;}
for(;t;t--)
  {w<<x<<y;
  w<<d[x][y]<<"\n";}
return 0;}