#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int n,i,k,t,d[1000001][8];
int c[1000001];
void ciur();


int main()
{
    ciur();
    fin>>t;
    for(i=1; i<=t; ++i)
    {
        fin>>n>>k;
        fout<<d[n][k]<<"\n";
    }

    return 0;
}



void ciur()
{
    d[1][0]=1;
    for(int i=2; i<=1000000; i++)
    {
        if(c[i]==0)
        {
            for(int j=i; j<=1000000; j+=i)
                c[j]++;


        }

        for(int j=0; j<=7; ++j) d[i][j]=d[i-1][j];
        d[i][c[i]]=i;

    }


}