#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fi("/home/keloo/Algorithms/divprim.in");
ofstream fo("/home/keloo/Algorithms/divprim.out");

const int sieveLimit = 1000000;
int sieve[sieveLimit+1];
vector <int> primes;

void generateSieve() {
	for (int i=2; i<sieveLimit; i++) {
		if (!sieve[i]) {
			primes.push_back(i);
			for (int j=i+i; j<sieveLimit; j+=i) {
				sieve[j] = 1;
			}
		}
	}
}

int divisorCount(int x) {
	int ans = 0;
	int i = 0;
	while ((i<primes.size()) && (x>1)) {
		if (x%primes[i] == 0) ans++;
		while (!(x % primes[i])) x /= primes[i];
		i++;
	}

	return ans;
}

int searchProcess(int left, int right, int k) {
	int mid=(left+right)/2;
	if (left == right) {
		if (divisorCount(left) == k) {
			return left;
		} else {
			return 0;
		}
	}
	int betterSolution = searchProcess(mid+1, right, k);
	if (betterSolution) {
		return betterSolution;
	} else if (divisorCount(mid) == k) {
		return mid;
	} else {
		return searchProcess(left, mid, k);
	}
}

int findNumber(int n, int k) {
	return searchProcess(2,n,k);
}

int main() {

	int n,k,t;

	generateSieve();

	fi >> t;
	while (t--) {
		fi >> n >> k;
		fo << findNumber(n,k) << endl;
	}

	return 0;
}