#include <bits/stdc++.h>

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
//http://www.infoarena.ro/problema/divprim
int dp[1000080][9],v[1000008];
inline void get_div()
{
    int i;
    for( i=2;i<=1000000;i++)
     if(v[i]==0)
        for(int j=i;j<=1000000;j=j+i)
         v[j]++;
}
int main()
{  long long int t,n,i,j,k;
    in>>t;
    get_div();
    for(int i=1;i<=1000000;i++)
        for(int j=0;j<=7;j++)
    {
      dp[i][j]=dp[i-1][j];
      if(v[i]==j)dp[i][j]=i;
    }
    while(t--)
    {
        in>>n>>k;
        out<<dp[n][k]<<'\n';
    }
    return 0;
}