#include<fstream>
#include<vector>
#include<vector>
#include<cstdlib>
#include<iostream>
using namespace std;
vector<int>v(1000002,0);
vector<int>haha[10];
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=1;j*i<=1000000;j++)
			v[i*j]++;
		if(v[i]>=0&&v[i]<=7)
			haha[v[i]].push_back(i);
	}
}
int cautare_binara(vector<int>vec,int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(x<vec[st])
		return 0;
	else
		if(vec[mij]==x)
			return vec[mij];
		else
		if(vec[mij]<x)
		{
			if(dr-mij==1)
				return vec[mij];
			else
				return cautare_binara(vec,mij+1,dr,x);
		}
		else
			if(vec[mij]>x)
			{
				if(mij-st==1)
					return vec[st];
				else
					return cautare_binara(vec,st,mij-1,x);
			}
}
int main()
{
	int j,i,N,K,T,lungime;
	ciur();
	f>>T;
	for(i=1;i<=T;i++)
	{
		f>>N>>K;
		lungime=haha[K].size()-1;
		g<<cautare_binara(haha[K],0,lungime,N)<<endl;
	}
	f.close();g.close();
	return 0;
}