#include <fstream>

using namespace std;
int n,k,t,v[2][1000005],v1[8][300005],i,st,dr,m;
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    for(i=4; i<=1000000; i+=2)
    {
        v[0][i]=1;
        v[0][i-1]=1;
        v[1][i]=i;
        v[1][i-1]=i-1;
    }
    v[0][2]=1;
    v[0][1]=0;
    i=1;
    while(i<998)
    {
        i+=2;
        while(v[0][i]!=1)
            i+=2;
        for(k=i*2; k<=1000000; k+=i)
        {
            while(v[1][k]%i==0)
            {
                v[1][k]/=i;
            }
            v[0][k]++;
            if(v[1][k]==1) v[0][k]/=2;
        }
    }
    for(i=2; i<=1000000; i++)
    {
        if(v[0][i]<=7)
        {
            v1[v[0][i]][0]++;
            v1[v[0][i]][v1[v[0][i]][0]]=i;
        }
    }
    f>>t;
    while(t)
    {
        t--;
        f>>n>>k;
        st=1;
        dr=v1[k][0];
        while(st+1<dr)
        {
            m=(st+dr+1)/2;
            if(v1[k][m]>n)
            dr=m;
            else st=m;
        }
        if(v1[k][dr]>n) dr=st;
        g<<v1[k][dr]<<'\n';
    }
    f.close(); g.close();
}