#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int n;
int ndp[1000001];
int sol[8][1000001];


int main()
{
    fin>>n;
    int i,r,q;
    int j;

    for(i=2;i<=1000000;i++)
        if(ndp[i]==0)
        for(j=i;j<=1000000;j=j+i)
        ndp[j]++;

    for(i=1;i<=1000000;i++)
        sol[ndp[i]][i]=i;

   for(i=1;i<=7;i++)
         for(j=1;j<=1000000;j++)
            if(sol[i][j]!=j)
            sol[i][j]=sol[i][j-1];

   for(i=1;i<=n;i++)
   {
       fin>>q>>r;
       fout<<sol[r][q]<<'\n';
   }



    return 0;
}