#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;			
}