#include <fstream>
using namespace std;
ifstream in ("divprim.in");
ofstream out("divprim.out");
int prim (int n)
{
    int d;
    if (n<2)
        return false;
    for (d=2; d*d<=n; d++)
        if (n%d==0)
            return false;
    return true;
}
int ndp (int n)
{
    int d, cnt=0;
    for (d=2; d*d<=n; d++)
        if (n%d==0)
        {
            if (prim (d)==true)
                cnt++;
            if (prim((n/d))==true)
                cnt++;
            if (d==(n/d))
                cnt--;
        }
    return cnt;
}
int main()
{
    int n, i, t, k, j, semafor;
    in>>t;
    for (i=1; i<=t; i++)
    {
        in>>n>>k;
        semafor=true;
        for (j=n; j>=1 && semafor==true; j--)
        {
            if (ndp (j)==k)
            {
                out<<j<<'\n';
                semafor=false;
            }
        }
        if (semafor==true)
            out<<"0"<<'\n';
    }
    return 0;
}