#include <fstream>

using namespace std;

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

int ciur[1000001];
int v[1000001];
int main()
{
    int n , ok, a, b;
    fin >> n;
    ciur[2] = 1;
    ciur[1] = 0;
    ciur[0] = 0;
    v[1] = 0;
    v[0] = 0;
    for(int i = 3; i <= 1000000; i += 2)
        ciur[i] = 1;
    for(int i = 2; i * i <= 1000000; i++)
    {
        for(int j = i * i; j <= 1000000; j += i * 2)
            ciur[j] = 0;
    }
    for(int i = 2; i <= 1000000; i++)
    {
        if(ciur[i] == 1)
        {
            for(int j = i * 2; j <= 1000000; j += i)
                v[j]++;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        fin >> a >> b;
        ok = 0;
        for(int j = a; j >= 1; j--)
        {
            if (v[j] == b)
            {
                ok = 1;
                fout << j << "\n";
                break;
            }
        }
        if(ok == 0)
            fout << 0 << "\n";
    }
    return 0;
}