#include<fstream>
using namespace std;
int v[1000001],ma[1000001][8];
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    long n,i,c,x,y,j;
    for(i=2;i<=1000000;i++)
    {
        if(v[i]==0)
        {
            v[i]=1;
            c=i+i;
            while(c<=1000000)
            {
                v[c]++;
                c=c+i;
            }
        }
    }
    ma[1][0]=1;
    for(j=2;j<=1000000;j++)
   {


    for(i=0;i<=7;i++)
    ma[j][i]=ma[j-1][i];
    ma[j][v[j]]=j;
   }
   f>>n;
   for(i=1;i<=n;i++)
   {
       f>>x>>y;
       g<<ma[x][y]<<endl;
   }



}