#include <stdio.h>
#include <math.h>

int div(int n)
{
int d=2;
int m=n;
int 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;
FILE *in=fopen("divprim.in","r");
FILE *out=fopen("divprim.out","w");
fscanf(in,"%d",&t);
while(t)
{
fscanf(in,"%d %d",&nr,&d);
int 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;
}