#include <fstream>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int NMAX=1000000;

char ciur[NMAX+5];

int rez[8][NMAX+1];

int main()
{
    int i, j, t, a, b;
    for(i=2;i<=NMAX;i++)
    {
        if(ciur[i]==0)
        {
            for(j=i;j<=NMAX;j+=i)
            {
                ciur[j]++;
            }
        }
    }

    for (int k=0; k<=7; k++)
    {
        rez[k][0]=0;
        for (int x=1; x<=NMAX; x++)
        {
            if (ciur[x]==k)
                rez[k][x]=x;
            else
                rez[k][x] = rez[k][x-1];
        }
    }
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<rez[b][a]<<endl;
    }
    return 0;
}