#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

ifstream fi("divprim.in");
ofstream fo("divprim.out");

const int sieveLimit = 1000001;
int sieve[sieveLimit+1];
int a[sieveLimit][8];


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


int main() {

	int n,k,t;

	generateSieve();

	for (int i = 1; i < sieveLimit; ++i) {
		for (int j = 0; j < 8; ++j) {
			if (sieve[i] == j) {
				a[i][j] = i;
			} else {
				a[i][j] = a[i-1][j];
			}
		}
	}



	fi >> t;
	while (t--) {
		scanf("%d%d", &n, &k);
		fo << a[n][k] << endl;
	}

	return 0;
}