#include <bits/stdc++.h>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,m,k;
bool ok=true;
int prim(int x)
{
    int nr=0;
    for(int d=2; d*d<=x; d++)
        if(x%d==0)
        {
            nr++;
            while(x%d==0)
                x/=d;
        }
    if(x>1&&nr!=0)
        nr++;
    return nr;
}

int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>m>>k;
        for(int j=m; j>0&&ok==true; j--)
            if(prim(j)==k)
            {
                g<<j<<'\n';
                ok=false;
                continue;
            }
        if(ok==true)
            g<<"0\n";
        ok=true;
    }
    return 0;
}