#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int v[1000001],a[1000001][8],q,n,k,t,ok,pr[1000001],m[1000001][8];
long long i,j;
int main()
{

    for(i=2; i<=1000001; i++)
       {
        if(v[i]==0)
            for(j=i; j<=1000001; j+=i)
            v[j]++;
             a[i][v[i]]=i;
       }
        for(j=1;j<=7;j++)
        for(i=1;i<=1000001;i++) if(a[i][j]==0) a[i][j]=a[i-1][j];
    f>>t;
    for(i=1; i<=t; i++)
    {
        f>>n>>k;
        g<<a[n][k]<<'\n';
    }

    return 0;
}