#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int factprim(int n)
{
    int cnt = 0,d=2,exp=0;
    while(n > 1)
    {
        exp = 0;
        while(n % d == 0)
        {
            exp++;
            n /= d;
        }
        if(exp > 0){
            cnt++;
        }
        if(n > 1){
           d = n;
        }
    }
    return cnt;

}
int main()
{
    int n,r=0,pas,t,k,i;
    cin >> t;

    for(i=0; i<t; i++)
    {
        cin >> n >> k;
        pas = 1 << 15;
        while(pas!=0)
        {
            if(factprim(r+pas) == k && r+pas < n){
                r+=pas;
            }
            pas /= 2;
        }
        cout << r <<"\n";
    }
    return 0;
}