#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int N=1000001;

char c[N];
void ciur(int n)
{
	int i,j;
	for(i=2;i*i<=n;i++)
		if(c[i]==0)
			for(j=i;j<=n;j=j+i)
				c[j]=c[j]+1;
};

int numar(int n,int k)//returneaza cel mai mare nr mai mic sau egal cu n, avand k divizori
{
	for(int i=n ; i>=1 ; --i)
		if(c[i] == k)
			return i;
	return 0;
}

int main()
{
	int t,n,k,i,j,r;
	cin>>t;
	ciur(N-1);
	for(i=1;i<=t;i++)
	{
		r=0;
		cin>>n;
		cin>>k;
		cout<<numar(n,k)<<"\n";
		/*
		if(k==1)
			k=0;
		for(j=n;j>=2;j=j-1)
			if(c[j]==k)
			{
				cout<<j<<"\n";
				j=0;
				r=1;
			}
		if(r==0)
			cout<<"0 \n";
		*/
	}
	return 0;
}