#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int nrdiv (int n)
{
    int d, p, cnt=0;
    for(d=2; d*d<=n; ++d)
    {
        p=0;
        while(n%d==0)
        {
            p++;
            n/=d;
        }
        if(p>0)
            cnt++;
    }
    if(n>1)
    cnt++;
    return cnt;
}

int gasit (int n, int k)
{
    int nr=n-1;
    while( nrdiv(nr)!=k && nr>1 )
    {
        nr--;
    }
    if(nr==1)
        return 0; //nu exista
    return nr;
}
int main()
{
    int t, n, k;
    in>>t;
    for(int i=1; i<=t; ++i)
    {
        in>>n>>k;
        out<<gasit(n,k)<<'\n';
     //  cout<<n<<" "<<nrdiv(n)<<'\n';
    }
    return 0;
}