#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
#define N 1000000
int t,n,k,c[1000001],a[1000001][8];
void ciur()
{
  for(int i=2;i<=N;i++)
    if(c[i]==0)
      for(int j=i;j<=N;j+=i)
        c[j]++;
}

void umple()
{
    for(int i=1;i<=N;i++)
    {
      for(int j=0;j<=7;j++)
        if(c[i]==j)
          a[i][j]=i;
        else
          a[i][j]=a[i-1][j];
    }
}
int main()
{
    ciur();
    umple();
    fin>>t;
    for(int i=1;i<=t;i++)
    {
     fin>>n>>k;
     fout << a[n][k] <<'\n';
    }
    return 0;
}