#include <fstream>

using namespace std;
ifstream in ("divprim.in");
ofstream out ("divprim.out");
int v[1000001];
int main()
{
    int t;
    in>>t;
    int i,j,k,n,cn;
    bool a=0;
    v[0]=v[1]=0;
    for(i=2;i<=1000000;i++)
    if(v[i]==0)
    for(j=i;j<=1000000;j+=i)
    v[j]++;
    for(i=1;i<=t;i++)
    {
        in>>n>>k;
        cn=n;
        a=0;
        while(cn)
        {
            if(v[cn]==k)
            {
                a=1;
                break;
            }
            cn--;
        }
        if(a==0)
        out<<0<<'\n';
        else
        out<<cn<<'\n';
    }
    return 0;
}