#include <stdio.h>

int div(int n)
{
int d=2,m=n,nr=0,mult=0;

while (1)
	{
	if (m%d==0) {++mult;m/=d;}
	else
		{
		if (mult>0) ++nr;
		mult=0;
		if (d==2) d=3;
		else d+=2;
		if (m==1) break;
		}
	}
return nr;
}		

int main()
{
int nr,d,t,gasit;
FILE *in=fopen("divprim.in","r");
FILE *out=fopen("divprim.out","w");
fscanf(in,"%d",&t);
while(t)
{
fscanf(in,"%d %d",&nr,&d);
gasit=0;
for ( ;nr>=2;--nr)
	if (div(nr)==d) {fprintf(out,"%d\n",nr);gasit=1;break;}
if (!gasit) fprintf(out,"0\n");
--t;
}

fclose(in);fclose(out);
return 0;
}