#include<stdio.h>
long prim[500000],v[1000001];
long nrprim = 0;

long div(long a)
{
	long val = 0;
	for(long i = 1; a > 1; i++)
	{
		if(a%prim[i] == 0)
		{
			val++;
			while(a%prim[i]==0) a/= prim[i];
		}
	}
	return val;
}

long afis1(long a,long b)
{
	if(b==0 && a >= 1) return 1;
	for(long i = a; i>=2; i--)
		if(div(i) == b) return i;
	return 0;
}

long afis2(long a,long b)
{
	if(b==0 && a >= 1) return 1;
	for(long i = a; i>=2; i--)
		if(v[i] == b) return i;
	return 0;
}
void calc()
{
	long j;
	prim[++nrprim] = 2;
	for(long i = 3; i < 1000000; i+=2)
	{
		if(v[i] == 1) continue; 
		prim[++nrprim] = i;
		long p = 1000000/i;
		for(j=i; j <= p ; j+=2)
			v[i*j] = 1;
	}
}
void calc2()
{
	long j;
	
	for(long i = 2; i < 1000000; i++)
	{
		if(v[i] >= 1) continue; 
		//prim[++nrprim] = i;
		long p = 1000000/i;
		for(j=1; j <= p ; j++)
			v[i*j]++;
	}
}


int main()
{
	long nrcaz,n,k;
	
	
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	
	calc2();
	scanf("%ld",&nrcaz);
	for(long ii = 1; ii <= nrcaz; ii++)
	{
		scanf("%ld %ld",&n,&k);
		printf("%ld\n",afis2(n,k));
	}
	
	return 0;
}