#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int a[1000002];
int i,n,k,j,t,ok;
int main()
{
    fin>>t;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            for(j=i+i;j<=1000000;j=j+i)
            {
                a[j]++;
            }
        }
    }
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        ok=0;
        for(j=n;1<=j;j--)
        {
            if(a[j]==k)
            {
                ok=1;
                fout<<j<<"\n";
                break;
            }

        }
        if(ok==0)
        {
            fout<<0<<"\n";
        }

    }
    fin.close();
    fout.close();
    return 0;
}