#include<iostream>
#include<cstdio>
#include<fstream>
using namespace std;
int t,n,k,c[1000001];

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

int main ()
{
ciur();
ifstream fin ("divprim.in");
freopen("divprim.out","w",stdout);
fin>>t;
while(t){
fin>>n>>k;
int gasit=0;
for(int i=n;i>=1&&gasit==0;--i)
	if(c[i]==k)
		gasit=i;
	printf("%d\n",gasit);
	
--t;}
fin.close();
return 0;}