#include <fstream>

using namespace std;
int n,k,t,v[3][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]=2;
        v[0][i-1]=1;
        v[1][i]=i;
        v[1][i-1]=i-1;
        v[2][i]=1;
        while(v[1][i]%2==0)
            v[1][i]/=2;
    }
    for(i=2; i<=1000000; i*=2)
        v[0][i]--;
    v[0][2]=1;
    v[0][1]=0;
    i=1;
    while(i<=998)
    {
        i+=2;
        while(v[2][i])
            i+=2;
        for(k=i*2; k<=1000000; k+=i)
        {
            v[2][k]=1;
            while(v[1][k]%i==0)
            {
                v[1][k]/=i;
            }
            v[0][k]++;
            if(v[1][k]==1) v[0][k]--;
        }
        i+=0;
    }
    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;
        }
    }
    v1[0][0]=1;
    v1[0][1]=0;
    f>>t;
    while(t)
    {
        t--;
        f>>n>>k;
        if(v1[k][1]<=n)
        {
            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';
        }
        else g<<"0\n";
    }
    f.close(); g.close();
}