#include <fstream>
#include <bitset>
using namespace std;
#define dim 1000001
bitset<dim>v;
int a[dim];
int q[8][dim];
int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	int t;
	fin>>t;
	int  n, p, i;
	
	
	for(int i=2;i<=dim;++i)
	{
		a[i]+=1;
		++i;
	}
	
	for(i=2;i<dim;++i)
	{
		++i;
		if(!v[i])
			for(int j=i;j<=dim;j+=i)
			{
					v[j]=1;
					a[j]+=1;
			}
		
	}
	
	for(i=0;i<=7;++i)
		q[i][0]=1;
	
	
	for(int m=2;m<=dim;++m)
	{
		
		q [ a[m] ][ q[a[m]][0]]= m;
		++q[a[m]][0];
	}
	
	
	for(int k=1;k<=t;++k)
	{
		fin>>n >>p;
		
		
		int ls=1;
		int ld=q[p][0];
		int mijloc=(ls+ld)/2;
		while(ls+1<ld)
		{
			mijloc=(ls+ld)/2;
			
			if(q[p][mijloc]<n)
					ls=mijloc;
			else
				if(q[p][mijloc]>n)
					ld=mijloc;
		}
		if(q[p][1]<n)	
		fout<<	q[p][ls] <<'\n';
		else
			fout<<"0" <<'\n';
		
	
	}
	
	return 0;
}