#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
char c[1000000]={0};
void ciur()
{
	int i,j,b=1000000;
	for(i=2;i<=b;i++)
		if(c[i]==0)
			for(j=i;j<=b;j=j+i)
				if(c[j]!=9)
					c[j]=c[j]+1;
};
	
int main()
{
int t,n,k,i,j,r;
cin>>t;
for(i=1;i<=t;i++)
{r=0;
	cin>>n;
	cin>>k;
	ciur();
	for(j=n;j>=2;j=j-1)
		if(c[j]==k)
		{
			cout<<j<<"\n";
			j=0;
			r=1;
		}
		if(r==0)
			cout<<"0 \n";
}
return 0;
}