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

#define NMAX 1000001
#define KMAX 8

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

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

int cbin(int n, int k)
{
	int pp,q,mij,sol;
	if(v[k].size()==0)
		return 0;
	if(v[k][0]>n)
		return 0;
	pp=0;
	q=v[k].size()-1;
	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;
	built(1000000);
	for(i=1;i<=t;i++) {
		f>>n>>k;
		g<<cbin(n,k)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}