#include <fstream>
#include <bitset>
using namespace std;
#define dim 1000001
bitset<dim>v;
int a[dim];
int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	int t;
	fin>>t;
	int f=0, gasit, n, p;
	
	
	for(int i=2;i<=dim;++i)
	{
		a[i]+=1;
		++i;
	}
	
	for(int i=2;i<dim;++i)
	{
		++i;
		if(!v[i])
			for(int j=i;j<=dim;j+=i)
			{
					v[j]=1;
					a[j]+=1;
			}
		
	}
	
	for(int k=1;k<=t;++k)
	{
		fin>>n >>p;
		gasit=0;
		while(gasit==0 && n>1)
		{
			if(a[n]==p)
			{gasit=1;fout<<n <<'\n';}
			--n;
		}
		if(gasit==0)
			fout<<0 <<'\n';
	
	}
	
	return 0;
}