#include <fstream>
using namespace std;
int t,n,k;
int v[1000001];

int m[8][1000001];
fstream fin ("divprim.in",ios::in);
fstream fout("divprim.out",ios::out);

int find(int n,int k){
	if (k == 0) return 1;
	if (m[k][m[k][0]] < n) return m[k][m[k][0]];
	int st,dr,mij;
	st = 1; dr = m[k][0];
	for (;st<=dr;){
		mij = st + (dr-st)/2;
		if (m[k][mij] <= n && m[k][mij+1] > n) return m[k][mij];
		if (m[k][mij] > n) dr = mij - 1;
		else if (m[k][mij] < n) st = mij + 1;
		
	};
	return 0;


};

int main(){
	fin>>t;
	for (int i = 2; i <= 1000000; i++)
		if (v[i] == 0)
			for( int j = 2 * i; j <= 1000000; j = j + i)
				v[j]++;
	for (int i = 2;i <= 1000000; i++)
		switch (v[i]){
			case 0 :m[1][0]++;
					m[1][ m[1][0] ] = i;
					break;
			case 1 :m[1][0]++; 
					m[1][ m[1][0] ] = i;
					break;
			case 2 :m[2][0]++; 
					m[2][ m[2][0] ] = i;
					break;
			case 3 :m[3][0]++; 
					m[3][ m[3][0] ] = i;
					break;
			case 4 :m[4][0]++; 
					m[4][ m[4][0] ] = i;
					break;
			case 5 :m[5][0]++; 
					m[5][ m[5][0] ] = i;
					break;
			case 6 :m[6][0]++; 
					m[6][ m[6][0] ] = i;
					break;
			case 7 :m[7][0]++; 
					m[7][ m[7][0] ] = i;
					break;
	};

	for (int i = 1; i <= t; i++){
		fin >>n>>k;
		fout<<find(n,k)<<'\n';
	};



};