#include <bits/stdc++.h>
using namespace std;

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

long long fr[1000005];
int n, x, k;

int main()
{
    int i, j;
    fin >> n;
    fr[0] = fr[1] = 1;
    for(i=2; i*i<=1000000; i++)
        if(fr[i] == 0)
            for(j=2; j*i<=1000000; j++)
                fr[j * i]++;
    for(i=1; i<=n; i++)
    {
        fin >> x >> k;
        if(x == 0 || x == 1) fout << "0\n";
        else if(fr[x] == 0) fout << x << "\n";
        else
        {
            for(j=x; j>=1 && fr[j] != k; j--)
                ;
            fout << j << "\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}