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

const int sieveLimit = 1000001;
int sieve[sieveLimit+1];
int a[sieveLimit+1][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;

	FILE *fi = fopen("divprim.in", "r");
	FILE *fo = fopen("divprim.out", "w");

	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];
			}
		}
	}


	fscanf(fi,"%d", &t);
	while (t--) {
		fscanf(fi,"%d%d", &n, &k);
		fprintf(fo,"%d\n", a[n][k]);
	}

	return 0;
}