#include <fstream>
//#include <iostream>

using namespace std;
int p[1000099],a[1000099][9];
int main()
{
   int t,k,n,i,j;
   for(i=2;i<=1000000;i+=2)
        p[i]++;
   for(i=3;i<=1000000;i+=2)
    {
        if(p[i]==0)
            for(j=i;j<=1000000;j+=i)
                p[j]++;
    }
    for(i=2;i<=1000000;i++)
        {
        for(j=1;j<=7;j++)
            a[i][j]=a[i-1][j];
        a[i][p[i]]=i;
        }
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>t;
    for(i=1;i<=t;i++)
        {
            fin>>n>>k;
            fout<<a[n][k]<<"\n";
        }
    fin.close();
    fout.close();
    return 0;
}