#include <iostream>
#include<fstream>
using namespace std;
int divizor(int n)
{
    int d,j,k=0,prim;
    for(d=2;d<=n/2;d++)
    {
        if(n%d==0)
        {
            prim=0;
            for(j=2;j<=d/2;j++)
                if(d%j==0)
                prim=1;
            if(prim==0)
                k++;
        }
    }
    return k;
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int T,N,K,i,ok,j,k,copie;
    f>>T;
    for(i=1;i<=T;i++)
    {
        f>>N>>K;
        copie=N;

        while(divizor(N)!=K && N>0)
        {

            N--;
        }
        g<<N<<endl;

    }

    return 0;
}