#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

#define N 100005
int c[N + 5];
void ciur()
{
    c[0] = c[1] = 0;
    c[2] = 1;
    for(int i = 4; i <= N; i += 2)
        c[i] = 0;
    for(int i = 3; i <= N; i += 2)
        c[i] = 1;
    for(int i = 3; i * i <= N; i += 2)
        if(c[i])
            for(int j = 3 * i; j <= N; j += 2 * i)
                c[j] = 0;
}

int T, n, k;
int NrDivPrimi(int n, int k)
{
    int cnt = 0, i;
    for(i = 1; i * i < n; i ++)
        if(n % i == 0)
        {
            if(c[i])
                cnt++;
            if(c[n / i])
                cnt++;
            if(cnt > k)
                return k + 1;
        }
    if(i * i == n && c[i])
        cnt++;
    return cnt;
}
int main()
{
    fin >> T;
    ciur();
    for(int i = 1; i <= T; i++)
    {
        fin >> n >> k;
        bool ok = 0;
        while(n)
        {
            if(NrDivPrimi(n, k) == k)
            {
                fout << n << "\n";
                ok = 1;
                break;
            }
            else
                n--;
        }
        if(!ok)
            fout << 0 << "\n";
    }
    return 0;
}