#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
#define N 1000000
int ciur[N+1];
int a[N+1][8];
int main()
{
    int t,n,k,i,j;
    int nrop=0;
    cin>>t;
    for(i=2;i<=N;i++)
      if(ciur[i]==0){
        for(j=i;j<=N;j+=i){
          ciur[j]++;
          nrop++;
        }
      }
    for(i=1;i<=N;i++)
    {
      for(j=0;j<=7;j++)
        if(ciur[i]==j)
          a[i][j]=i;
        else
          a[i][j]=a[i-1][j];
    }
    for(i=1;i<=t;i++)
    {
      cin>>n>>k;
      cout<<a[n][k]<<'\n';
    }
    return 0;
}