#include<cstdio>
int v[1000005],m[8][1000005],poz[8];
int main(){
  int i,j,n,nr,k,max;
  v[0]=v[1]=1;
  freopen("divprim.in","r",stdin);
  freopen("divprim.out","w",stdout);
  for(i=2;i<=1000000;i++)
  {
    if(v[i]==0){
    for(j=i;j<=1000000;j+=i)
      v[j]++;
    }
  }
for(i=1;i<=1000000;i++)
{
  m[v[i]][1+poz[v[i]]]=i;
  poz[v[i]]++;
}
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&nr,&k);
j=1;
max=-1;
while(m[k][j]<=nr){
if(m[k][j]>max)
max=m[k][j];
j++;
}
if(max!=-1)
printf("%d\n",max);
else
printf("0\n");
}
return 0;
}