#include <cstdio>
#define Nmax 1000055
using namespace std;
int t,Q[Nmax],v[Nmax],dp[Nmax][8];
void ciur(){
 int i,j;
 for(i=2;i<=Nmax;i++)
  if(!v[i]){ Q[i]=1;
    for(j=i+i;j<=Nmax;j+=i){
     v[j]=1;Q[j]++;}}
}
void solve(){
int i,j;
 for(i=1;i<Nmax;i++)
  for(j=1;j<=7;j++){
    if(Q[i] == j)
     dp[i][j] = i;
     else dp[i][j]=dp[i-1][j];
  }
}
int main(){
    int i,n,k,j;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    ciur();
    solve();
    for(i=1;i<=t;i++){
      scanf("%d%d",&n,&k);
      printf("%d\n",dp[n][k]);
    }
    return 0;
}