#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");


int prim(int n)
{
    int nd=0;
    for(int i=1;i<=n;i++)
        if(n%i==0)
           nd++;
    if(nd==2)
        return 1;
    else
        return 0;
}

int div(int n)
{
    int cnt=0;
    for(int d=1;d*d<=n;d++)
        if(n%d==0)
        {
            if(prim(d)==1)
                cnt++;
            if(d*d<n)
                if(prim(n/d)==1)
                     cnt++;
        }
    return cnt;

}
int main()
{
    int T, N[1001], K[101];
    fin>>T;
    for(int i=1;i<=T;i++)
        fin>>N[i]>>K[i];
    for(int i=1;i<=T;i++)
    {
        int n=N[i], ok=0;
        while(ok==0 && n>=1)
        {
            if(div(n)==K[i])
                ok=1;
            else
                n--;
        }
        if(ok==1)
            fout<<n<<endl;
        else
            fout<<0<<endl;
    }
    return 0;
}