#include<iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

#define NMAX 1000001
#define KMAX 8

vector <int> v[KMAX];
int p[NMAX];
bitset <NMAX> d;

void ciur(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(d[i]==0) {
			for(j=i+i;j<=n;j=j+i)
				d[j]=1;
			p[++p[0]]=i;
		}
}

void built(int n)
{
	int nr,i,j;
	v[0].push_back(1);
	for(i=2;i<=n;i++) {
		nr=0;
		for(j=1;j<=p[0] &&  p[j]*p[j]<=i;j++)
			if(i%p[j]==0) {
				nr++;
				if(p[j]*p[j]<i && d[i/p[j]]==0)
					nr++;
			}
		if(d[i]==0)
			nr++;
		if(nr<=7)
			v[nr].push_back(i);
	}
}

int cbin(int n, int k)
{
	int pp,q,mij,sol,i;
	if(v[k].size()==0)
		return 0;
	if(v[k][0]>n)
		return 0;
	pp=0;
	q=v[k].size()-1;
	//for(i=0;i<=q;i++)
		//cout<<v[k][i]<<" ";
	//cout<<endl;
	sol=0;
	while(pp<=q) {
		mij=(pp+q)/2;
		if(v[k][mij]<=n) {
			sol=v[k][mij];
			pp=mij+1;
		}
		else q=mij-1;
	}
	return sol;
}

int main ()
{
	int t,n,k,i;
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	f>>t;
	ciur(1000000);
	built(200000);
	for(i=1;i<=t;i++) {
		f>>n>>k;
		g<<cbin(n,k)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}