#include <fstream>
#include <vector>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int viz[1000002];
int t,n,nr,k;

#define NMAX 1000000
vector <vector<int> >a;
void ciur()
{
    a.resize(8);
    int i,d;
    for(i=1;i<=7;i++)
        a[i].push_back(0);

    for(i=2;i<=NMAX;i+=1)
    {
        if(viz[i]==0)
        {

            for(d=i;d<=NMAX;d+=i)
                viz[d]++;
            a[1].push_back(i);
            a[1][0]++;


        }
        else
        {
            if(viz[i]<=7)
            {
            a[viz[i]].push_back(i);
            a[viz[i]][0]++;
            }
        }

    }
}
int binar(int p,int q)
{
    if(p>=q)
    {
        return p;
    }
    else
    {
        if(a[k][(p+q)/2]>n)
            return binar(p,(p+q)/2-1);
        else if(a[k][(p+q)/2]<n)
        {
            return binar((p+q)/2+1,q);
        }
        else return (p+q)/2;
    }
}
void citire()
{
    int i;
    fin>>t;
    while(t)
    {
        int x;
        fin>>n>>k;
        x=binar(1,a[k][0]);
        while(a[k][x]>n)
        {
            x--;
        }
        while(a[k][x+1]<n&& x<a[k][0])
        {
            x++;
        }
        fout<<a[k][x]<<'\n';
        t--;
    }
}
int main()
{
    ciur();
    citire();

    return 0;
}