#include <fstream>

using namespace std;
ifstream cin ("divprim.in");
ofstream cout ("divprim.out");
int t,n,k,i,d,ciur[1000050],ok,j;
int main()
{
    for (i=2; i*i<=1000000; i++)
    {
        if (ciur[i]==0)
        {
            for (d=i; d<=1000000; d=d+i)
            {
                ciur[d]++;
            }
        }
    }
    cin >>t;
    for (i=1; i<=t; i++)
    {
        cin >>n>>k;
        ok=0;
        for (j=n-1; j>=1; j--)
        {
            if (ciur[j]==k) {cout <<j<<'\n'; ok=1; break;}
        }
        if (ok==0) {cout <<ok<<'\n';}
    }
    return 0;
}