#include <fstream>
#define IN "divprim.in"
#define OUT "divprim.out"
#define MAX 1000005
#include <iomanip>

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int TEST, N, K;
int ok[MAX], T[MAX][7];

void ciur()
{
	int i, j;
	for(i=2; i<=MAX; ++i)
		if(ok[i]==0)
			for(j=i; j<=MAX; j+=i)
				++ok[j];
	for(i=1; i<=MAX; ++i)
		for(j=1; j<=7; ++j)
			if(ok[i]==j)
				T[i][j]=i;
			else
				T[i][j]=T[i-1][j];
}

void scrie()
{
	if(K>7||K<1)
		out<<"0\n";
	else
		out<<T[N][K];
}

int main()
{
	in>>TEST;
	ciur();
	while(TEST)
	{
		in>>N>>K;
		scrie();
		--TEST;
	}
	in.close();
	out.close();
	return 0;
}