#include <fstream>

using namespace std;
int n,t,k,i,j,c[1000001];
ifstream fin("divprim.in");
ofstream fout("divprim.out");

void ciur()
{
    for(j=2; j<=1000000; j+=2)
        c[j]++;
    for( i=3; i<=1000000; i+=2)
    {
        if(c[i]==0)
            for( j=i; j<=1000000; j+=i)
                c[i]++;
    }
}
int main()
{
    ciur();
    fin>>t;
    for(i=1; i<=t; i++)
    {
        fin>>n>>k;
        for(j=n; j>2; j--) if(c[j]==k)
            {
                fout<<j<<'\n';
                break;
            }
        if(j<=2) fout<<0<<'\n';
    }
    return 0;
}