#include <bits/stdc++.h>

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int nr[1000010], T, N, K;
int main()
{
    for(int i = 4;i <= 1000000;i++)
    {
        int n = i;
        for(int d = 2;d * d <= n;d++)
        {
            if(n % d == 0) nr[i]++;
            while(n % d == 0) n /= d;
        }
        if(n > 1) nr[i]++;
    }
    in >> T;
    for(int i = 1;i <= T;i++)
    {
        in >> N >> K;
        bool OK = true;
        for(int i = N;OK && i >= 1;i--)
            if(nr[i] == K)
        {
            OK = false;
            out << i << '\n';
        }
        if(OK) out << 0;
    }
    return 0;
}