#include <iostream>
#include <fstream>
using namespace std;
int T,N,K,X,nr,ok=0;
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
    f>>T;
    for(int i=1;i<=T;i++)
    {
        f>>N;
        f>>K;
        X=N;

    while(X>0 && ok==0)
    {
        nr=0;
        if(X%2==0)
            nr=nr+1;
        for(int j=3;i<=N;j=j+2)
        {
            if(X%i==0)
                nr=nr+1;
        }
        if(nr==K)
            {g<<X<<endl;
            ok=1;}
        else
            {X=X-1;
            ok=0;}
    }
    if(X==0 && ok==0)
        g<<"0";
    }
    return 0;
}