#include <bits/stdc++.h>

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int nr[1000010], T, N, K, pr[1000010];
int main()
{
    pr[0] = pr[1] = 1;
    for(int i = 2;i <= 1000000;i++)
    {
        if(pr[i] == 0)
        {
            for(int j = i + i;j <= 1000000;j += i)
            {
                pr[j] = 1;
                nr[j]++;
            }
        }
    }
    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 << '\n';
    }
    return 0;
}