#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;
    f>>T;
    for(i=1;i<=T;i++)
    {
        f>>N>>K;ok=0;
        for(j=N;j>=2;j--)
        {
            if(divizor(j)==K)
            {
                ok=1;
                g<<j<<endl;
                break;
            }

        }
        if(ok==0)
            g<<0<<endl;
    }

    return 0;
}