#include<stdio.h>
#include<memory.h>
#pragma pack(push,1)
#define N 2010
int vanturile[N],put;
void ciuruletz_cu_lapte()
{
	int ICHB,PUTE,curcan[N];
	memset(curcan,0,sizeof(curcan));
	for(ICHB=2;ICHB*ICHB<N;++ICHB)
		if(!curcan[ICHB])
			for(PUTE=ICHB*ICHB;PUTE<N;PUTE+=ICHB)
				curcan[PUTE]=1;
	for(ICHB=2;ICHB<=N;++ICHB)
		if(!curcan[ICHB])
			vanturile[put++]=ICHB;
}
int da_mi_gogoasa(int porc_mistret_vanat_de_tiriac,int numarul_de_gloante)
{
	int nu_te_grabi_tiriacule=0;
	for(int i=0;vanturile[i]*vanturile[i]<put;++i)
	{
		nu_te_grabi_tiriacule=0;
		while(!(porc_mistret_vanat_de_tiriac%vanturile[i]))
		{
			porc_mistret_vanat_de_tiriac/=vanturile[i];
			if(!nu_te_grabi_tiriacule)
			{
				numarul_de_gloante--;
				nu_te_grabi_tiriacule=1;
			}
		}
	}
	if(porc_mistret_vanat_de_tiriac>1)
		--numarul_de_gloante;
	return (numarul_de_gloante)?0:1;
}
int da_mi_o_bere_ca_te_pun_in_recicle_bean(int firma_berii,int numarul_de_beri)
{
	int gaboru_cu_amprentele=numarul_de_beri;
	if(numarul_de_beri)
	for(int i=firma_berii;i>=2;--i)
	{
		gaboru_cu_amprentele=numarul_de_beri;	
		if(da_mi_gogoasa(i,gaboru_cu_amprentele))
			return i;
	}
	else
		return 1;
	return 0;
}
int main()
{
	int cheia_lui_portar,numarul_de_basini,purcica_merge_la_paris_cu_avionul;
	ciuruletz_cu_lapte();
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&purcica_merge_la_paris_cu_avionul);
	while(purcica_merge_la_paris_cu_avionul)
	{
		scanf("%d%d",&cheia_lui_portar,&numarul_de_basini);
		printf("%d\n",da_mi_o_bere_ca_te_pun_in_recicle_bean(cheia_lui_portar,numarul_de_basini));
		--purcica_merge_la_paris_cu_avionul;
	}
	return 0;
}