#include<stdio.h>
#define max 1000000
int ciur[max], sol[max], i, j, n, k, t, nr;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for (i=1;i*2<=max;i++)
		ciur[2*i]++;
	for (i=3;i<=max;i+=2)
		if (ciur[i]==0){
			j=1;
			while (i*j<=max){
				ciur[i*j]++;
				j++;
			}
		}
	for (nr=1;nr<=t;nr++){
		scanf("%d%d",&n,&k);
		for (i=1;i<=n;i++){
			sol[ciur[i]]=i;
		}
		printf("%d\n",sol[k]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}