#include<stdio.h>
#define dim 1000000
int a[dim],n,m,i,k;
void ciur()
{
 for(i=2;i<=dim/2;i++)
{
 if(a[i]==0)
 for(k=i+i;k<=dim;k+=i)
 a[k]++;
}}
void solve(int x,int y)
{int k;
 for(k=x-1;k>=1;k--)
 if(a[k]==y)
 {printf("%d\n",k);
 return ;
}
printf("0\n");}
int main ()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 scanf("%d",&n);
 int x,y,p;
 x=n;
 ciur();
 n=x;//printf("p %d \n",n);
 for(p=1;p<=n;p++)
 {scanf("%d%d",&x,&y);
 
 solve(x,y);
}
return 0;
}