//Divizori Primi
#include<fstream>
using namespace std;
   int main()
{  
    int t,n,j,i,k,a[100005],v[100005][11];  
    ifstream f("divprim .in");
    ofstream g("divprim.out");
     f>>t
     v[1][0]=0
    for (i=2;i<100005;i++)      
      if(a[i]==0)
{
    for (j=i;j<100005;j++)
      a[j]++;
}      
    for(j=0;j<=7;j++)
      v[i][j]=v[i-1=[j];
    if(a[i]<=7)
      v[i][a[i]]=i;
    for(i=1;i<=t;t++)
{ 
    f>>n>>k;
    fout<<v[n]pk]<<'\n';
}
    f.close();
    g.close();
    return 0;
}