#include <fstream>
#include <algorithm>

using namespace std;

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

long long ciur[1000001];
long long nrdiv[1000001];
long long v[8][100001];

int main()
{
	int n, p1 = 0, p2 = 0, p3 = 0, p4 = 0, p5 = 0, p6 = 0, p7 = 0, t, k,st, dr, mij = 1, sol;
	fin >> n, t, k;
	ciur[2] = 1;
	for(int i = 3; i <= 1000000; i += 2)
		ciur[i] = 1;
	for(int i = 3; i * i <= 1000000; i += 2)
	{
		if(ciur[i] == 1)
		{
			for(int j = i * i; j <= 1000000; j += i)
				ciur[j] = 0;
		}
	}
	for(int i = 2; i <= 1000000; i ++)
	{
		if(ciur[i] != 0)
		{
			for(int j = i; j <= 1000000; j += i)
				nrdiv[j]++;
		}
	}
	for(int i = 1; i <= 1000000; i++)
	{
		if(nrdiv[i] == 1)
		{
			p1++;
			v[nrdiv[i]][p1] = i;
		}
		else if(nrdiv[i] == 2)
		{
			p2++;
			v[nrdiv[i]][p2] = i;
		}
		else if(nrdiv[i] == 3)
		{
			p3++;
			v[nrdiv[i]][p3] = i;
		}
		else if(nrdiv[i] == 4)
		{
			p4++;
			v[nrdiv[i]][p4] = i;
		}
		else if(nrdiv[i] == 5)
		{
			p5++;
			v[nrdiv[i]][p5] = i;
		}
		else if(nrdiv[i] == 6)
		{
			p6++;
			v[nrdiv[i]][p6] = i;
		}
		else if(nrdiv[i] == 7)
		{
			p7++;
			v[nrdiv[i]][p7] = i;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		fin >> t >> k;
		if(k == 1)
			dr = p1;
		if(k == 2)
			dr = p2;
		if(k == 3)
			dr = p3;
		if(k == 4)
			dr = p4;
		if(k == 5)
			dr = p5;
		if(k == 6)
			dr = p6;
        	if(k == 7)
            		dr = p7;
		while ( st <= dr)
		{
			sol = v[k][mij];
			mij = (st + dr) / 2;
			if(v[k][mij] < t)
				st = mij;
			if(v[k][mij] > t)
				dr = mij;
		}
			fout << sol;
	}
	return 0;
}