#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int K=7+1;
const int N=1000000+1;
int lp[N],p[N],cnt=0;
int v[K][N];

int main()
{
    for(int i=1;i<N;i++)
        lp[i]=i;
    for(int i=2;i<N;i++)
    {
        if(lp[i]==i)
            p[++cnt]=i;
        for(int j=1;j<=cnt && p[j]<=lp[i] && i*p[j]<N;j++)
            lp[i*p[j]]=p[j];
    }
    for(int i=1;i<N;i++)
        lp[i]=0;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=p[i];j<N;j+=p[i])
            lp[j]++;
    }
    for(int i=1;i<N;i++)
    {
        int cnt=lp[i];
        if(cnt<K)
            v[cnt][i]=1;
    }
    for(int i=1;i<K;i++)
    {
        for(int j=1;j<N;j++)
            if(v[i][j]==1)
                v[i][j]=j;
            else
                v[i][j]=v[i][j-1];
    }
    int t;
    fin>>t;
    while(t--)
    {
        int x,cnt;
        fin>>x>>cnt;
        fout<<v[cnt][x]<<"\n";
    }
    return 0;
}