#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int t, n, k;

int divprim[8][1000002], sz[8];
 
bool prim[1000002];
int cnt[1000002]; 
void ciur()
{
	for(int i = 2; i <= 1000000; ++i)
	{
		if(!prim[i])
		{
			for(int j = i; j <= 1000000; j += i)
			{
				cnt[j]++;
				prim[j] = 1;
			}
		}
	}
	
	for(int i = 1; i <= 1000000; ++i)
	{
		int nr_div = cnt[i];
		sz[nr_div]++;
		divprim[nr_div][sz[nr_div]] = i;
	}
} 
 
int main()
{
	ciur();
	fin >> t;
	for(int i = 1; i <= t; ++i)
	{
		fin >> n >> k;
		int st = 1; 
		int dr = sz[k];
		int ans = 0;
		while(st <= dr)
		{
			int mid = (st + dr) / 2;
			if(divprim[k][mid] <= n)
			{
				ans = divprim[k][mid];
				st = mid + 1;
			}
			else
			{
				dr = mid - 1;
			}
		}
		fout << ans << '\n';
	}
	return 0;
}