#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const int lim=1000000;
vector<int> mat[8];
int v[lim+1];

void ciur()
{
	memset(v,0,sizeof(v));
	for(int i=2;i<=lim/2;i++)
	{
		if(v[i]==0)
		{
			v[i]++;
			for(int j=i+i;j<=lim;j+=i)
				v[j]++;
		}
	}
	for(int i=lim/2;i<=lim;i++)
		if(v[i]==0)
			v[i]++;
}	

void build()
{
	mat[0].push_back(1);
	
	for(int i=2;i<=lim;i++)
		if(v[i]<=7)
			mat[v[i]].push_back(i);
	for(int i=0;i<=7;i++)
		sort(mat[i].begin(),mat[i].end());
}
	
int search(int n,int k)
{
	int left=0,right=(int) mat[k].size()-1,sol=0;

	while(left<=right)
	{
		int mid=left+(right-left)/2;

		if(mat[k][mid]<=n)
		{
			sol=mat[k][mid];
			left=mid+1;
		}
		else
			right=mid-1;
	}
	return sol;
}
		
int main()
{
	int t,n,k;

	ifstream in("divprim.in");
	ofstream out("divprim.out");
	ciur();
	build();
	in>>t;
	
	for(int i=0;i<t;i++)
	{
		in>>n>>k;
		out<<search(n,k)<<"\n";
	}
	in.close();
	out.close();
}