#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int n,k,q,c[1000001],a[1000001][10];
void ciur()
{
    for(int i=2; i<=1000000; ++i)
        if(c[i]==0)
         for(int j=i; j<=1000000; j+=i)
            c[j]++;
}
int main()
{
    ciur();
    for(int i=1; i<=1000000; ++i)
        for(int j=1; j<=7; ++j)
            if(c[i]==j and i>a[i-1][j])
                a[i][j]=i;
            else
              a[i][j]=a[i-1][j];
    cin>>q;
    for(int i=1; i<=q; ++i)
        cin>>n>>k,cout<<a[n][k]<<"\n";
}