#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
int t,n,k,ciur[1000001],v[1000001][8];
int main()
{
    for (int i=2;i*i<=1000000;i++)
        {if (ciur[i]==0) {for (int j=i;j<=1000000;j=j+i)
                              {ciur[j]++;}}}
    fin >>t;
    for (int i=1;i<=1000000;i++)
        {for (int j=1;j<=7;j++)
              v[i][j]=v[i-1][j];
         v[i][ciur[i]]=i;}
    for (int i=1;i<=t;i++)
        {fin >>n>>k;
         fout <<v[n][k]<<'\n';}
    return 0;
}