#include<cstdio>

const int N=1<<20;

int c[N];

int a[10][N];

int n;

int cautare(int b, int x , int n2)
{
	int i,pas;
	for (pas=1;pas<=n2;pas<<=1); // Puterea lui 2 <n
	for (i=0; pas; pas>>=1)
		if (i+pas<=n2 &&  a[b][i+pas]<=x)
			i+=pas;
	if (i==0) return 0;
	return a[b][i];
}



int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);


	int i,j;
	for (i=2;i*i<N;++i)
		if (!c[i]) // daca este prim
			for (j=i;j<N;j+=i)
				c[j]++;


	for (i=2;i<N;++i)
	{
		if (c[i]==0) c[i]++;
		a[c[i]][ ++a[c[i]][0] ] = i;
	}
	
	scanf("%d", &n);
	
	int x,b,c2;
	
	for (i=1;i<=n;i++)
	{
		scanf("%d%d", &x ,&b);
		
		if (b==0) printf("1\n");
		else
		{			
		c2=cautare (b,x,a[b][0]);
		printf("%d\n", c2);
		}
	}
	

	return 0;
}