#include <iostream>
#include <fstream>
#include <vector>
 using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
 const int MAXN=1000000;
 int cnt[MAXN+1];
 int ans[8][MAXN+1];
void ciur()
{
for (int i=2;i<=MAXN;i++){
    if (cnt[i]==0){
    for (int j=i;j<=MAXN;j+=i)
        cnt[j]++;
    }
}
for (int k=0;k<=7;k++){
    for (int i=1;i<=MAXN;++i){
    if (cnt[i]==k)
     ans[k][i]=i;
     else
    ans[k][i]=ans[k][i-1];
}
}
}
 int main()
{
 int n,k;
 int t;
 ciur();
 fin>>t;
 while (t--)
 {
    fin>>n>>k;
    fout<<ans[k][n]<<'\n';
 }

 return 0;
}