#include <fstream>
#include <algorithm>
using namespace std;
 
int v[1000001], s[8][1000001], k[8];
int i, j, n, a, b;
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    for(i=2; i<=1000000; i++)
    {
        if(!v[i])
        {
            v[i]++;
            for(j=i+i; j<=1000000; j+=i)
            {
                v[j]++;
            }
        }
    }
    for(i=2; i<=1000000; i++)
    {
        k[v[i]]++;
        s[v[i]][k[v[i]]]=i;
    }
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>a>>b;
        g<<*(upper_bound(s[b]+1, s[b]+k[b]+1, a)-1)<<"\n";
    }
}