// 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<=DIM;i++)
		v[i]=0;
	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<<endl;break;}
		if(j==0) g<<0<<endl;
	}
}