#include<cstdio>
using namespace std;
int p[10000],q=0;
int func(int a, int nrd)
{
	int d=2, nd=0;
	while(a!=1)
	{
		if(a%d==0)
		{
			nd++;
			if(nd>nrd)return 0;
		}
		while(a%d==0)a=a/d;
		d++;
	}
	if(nd==nrd)return 1;
	return 0;
}
FILE *f=fopen("divprim.in","r"),*g=fopen("divprim.out","w");
int main()
{
	int i,T,n,nrd,j;
	fscanf(f,"%d",&T);
	for(i=1;i<=T;i++)
	{
		int a;
		fscanf(f,"%d %d",&n, &nrd);
		for(j=n;j>=2;j--)
		{
			a=func(j,nrd);
			if(a){fprintf(g,"%d\n",j);break;}
		}
		if(a==0)fprintf(g,"0\n");
	}	
	return 0;
}