//		http://infoarena.ro/problema/divprim
#include<fstream>
#include<math.h>
#define DIM 1000001

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");
int v[DIM];

void ciur()
{
	for(int i=2;i<=1000;i++)
		if(v[i]==0)
			for(int j=i+i;j<=DIM;j+=i)
				v[j]++;
}


int main()
{
	int t,k;
	f>>t;
	ciur();
	long int j,n;
	for(long int i=1;i<=t;i++)
	{
		f>>n>>k;
		for( j=n;j>=1;j--)
			if(v[j]==k) {g<<j;break;}
		if(j==0) g<<0;
	}
}