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

bool 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;
	for (int i = n;i >= 1; i--){
		if (m[k][i] == true) return i;
		
	};
	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][i] = true;
					break;
			case 1 : m[1][i] = true;
					break;
			case 2 : m[2][i] = true;
					break;
			case 3 : m[3][i] = true;
					break;
			case 4 : m[4][i] = true;
					break;
			case 5 : m[5][i] = true;
					break;
			case 6 : m[6][i] = true;
					break;
			case 7 : m[7][i] = true;
					break;
	};

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



};