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