#include<stdio.h>
#define N 1000006
int a[8][400000]={0};char c[1000001]={0};int main(){int p,u,m,n,t,i,j,k;freopen("divprim.in", "r", stdin);freopen("divprim.out", "w", stdout);scanf("%d", &t);for(i=2;i<N;++i)if(!c[i])for(j=i;j<N;j+=i)c[j]+=1;for(i=1;i<N;++i)a[c[i]][ ++a[c[i]][0] ]=i;for(i=1;i<=t;++i){scanf("%d%d", &n,&k);p=1;u=a[k][0];while(p<u){m=(p+u)/2;if(n<=a[k][m])u=m;else p=m+1;}if(a[k][p]>n) --p;if(p==0)printf("0\n");else printf("%d\n",a[k][p]);	}return 0;}