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