#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
bool c[500001];
int v[43000];
bool pg(int n,int k)
{
    int c=0;
    for(int i=0;v[i]<n/2;i++)
        if(n%v[i]==0)
           c++;
    if(c==k)
        return true;
    else
        return false;

}
void ciur()
{
    int r=0;
    for(int i=4;i<=500000;i+=2)
        c[i]=1;
    for(int i=3;i<=500000;i+=2)
    {
            if(c[i]==0)
           {
             v[r]=i;
            for(int j=2*i;j<=500000;j+=i)
                c[j]=1;
            }
    }
}
int main()
{
    int t,n,k;
    fin>>t;
    for(int i=0;i<t;i++)
    {
        fin>>n>>k;
        bool p=pg(n,k);
        while(!p&&n>1)
        {
            if(c[n]==0)
                n--;
            else
            {
                n--;
                p=pg(n,k);
            }

        }
        if(p==1)
            fout<<n<<'\n';
        else
            fout<<"0"<<'\n';

    }
    return 0;

}