#include<fstream>
#include<vector>
#include<cstdlib>
using namespace std;
vector<int>v(1000002,0);
int n;
ifstream f("divprim.in");
ofstream g("divprim.out");
void ciur()
{
	int i,j;
	for(i=2;i<=1000000;i++)
		if(v[i]==0)
		for(j=2;j*i<=1000000;j++)
			v[i*j]++;
}
int main()
{
	int j,i,N,K,T;
	ciur();
	f>>T;
	for(i=1;i<=T;i++)
	{
		f>>N>>K;
		for(j=N;j>=1;j--)
			if(v[j]==K)
			{
				g<<j<<endl;
				break;
			}
		if(j==0)
			g<<0<<endl;
	}
	f.close();g.close();
	return 0;
}