#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int ciur[1000005],t,n,k,i,j,d,p,u,mij,sol,v[10][1000005];
int main()
{
    ciur[1]=1;
    for(i=2;i<=1000000;i++)
    {
        if(ciur[i]==0)
        {
            for(d=i;d<=1000000;d=d+i)
            {
                ciur[d]++;
            }
        }
    }
    for (i=1;i<=1000000;i++)
    {
        if (ciur[i]==1) {v[1][0]++;v[1][v[1][0]]=i;}
        if (ciur[i]==2) {v[2][0]++;v[2][v[2][0]]=i;}
        if (ciur[i]==3) {v[3][0]++;v[3][v[3][0]]=i;}
        if (ciur[i]==4) {v[4][0]++;v[4][v[4][0]]=i;}
        if (ciur[i]==5) {v[5][0]++;v[5][v[5][0]]=i;}
        if (ciur[i]==6) {v[6][0]++;v[6][v[6][0]]=i;}
        if (ciur[i]==7) {v[7][0]++;v[7][v[7][0]]=i;}
    }
    for (i=1;i<=10;i++)
    {
        //cout <<v[1][i]<<" ";
    }
    cin >>t;
    for(i=1;i<=t;i++)
    {
        cin >>n>>k;
        p=1;
        u=n;
        sol=0;
        while (p<=u)
        {
            mij=(p+u)/2;//cout <<v[k][mij]<<" ";
            if (v[k][mij]<=n) {sol=v[k][mij];p=mij+1;}
            else u=mij-1;
        }
        cout <<sol<<'\n';
    }
    return 0;
}