#include<stdio.h>
#define max 1000010
int ciur[max], s, i, j, n, k, t, nr, ind[10], sol[10][max], p;
int caut(){
	int li=1, ls=ind[k], t;
	while (li<=ls){
		t=(li+ls)/2;
		if (sol[k][t]>n)
			ls=t-1;
		else 
		if (sol[k][t+1]>n||t==n)
			return sol[k][t];
		else 
			li=t+1;
	}
	return 0;
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for (i=2;i<=max;++i)
		if (ciur[i]==0){
			j=1;
			while (i*j<=max){
				ciur[i*j]++;
				j++;
			}
		}
		else
			sol[ciur[i]][++ind[ciur[i]]]=i;
	for (nr=1;nr<=t;nr++){
		scanf("%d%d",&n,&k);
		if (n<10000){
			s=0;
			for (i=n;i>1;i--)
				if (ciur[i]==k){
					printf("%d\n",i);
					s=1;
					break;
				}
			if (s==0) printf("0\n");
		}
		else{
			p=caut();
			printf("%d\n",p);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}