#include <stdio.h>
//#include <time.h>
#define NMAX 1000001

int n, k, t;
int a[NMAX], p[80000], nprimes, s;
int ord[8][NMAX/2], last;
void ciur() {
	int i, d;
	for (i = 2; i < NMAX; ++i)
		if (!a[i]) {
			for (d = 2; d * i <= NMAX; ++d)
				a[d*i] = 1;
		}
}
void comp() {
	int i, j;
	for (i = 2; i <= NMAX; ++i)
		if (!a[i])
			a[i] = 1;
		else {
			for (j = 0; i % p[j]; ++j)
				;
			if (i/p[j] % p[j] == 0)
				a[i] = a[i/p[j]];
			else 
				a[i] = a[i/p[j]] + 1;
		}
}
void search(int p, int q) {
	if (p <= q) {
		int m = (p + q)/2; 
		if (ord[k][m] == n)
			last = ord[k][m];
		else if (ord[k][m] < n) {
			last = ord[k][m];
			search(m+1, q);
		}
		else {
			search(p, m-1);
		}
	}
}
int main() {
	//clock_t begin, end;
	int i;
	FILE *fi = freopen("divprim.in", "r", stdin);
	FILE *fo = freopen("divprim.out", "w", stdout);
	scanf("%d", &t);
	//begin = clock();
	ciur();
	for (i = 2; i <= NMAX; ++i)
		if (!a[i])
			p[nprimes++] = i;
	comp();
	for (i = 0; i < 8; ++i)
		ord[i][0] = 1;
	for (i = 1; i < NMAX; ++i)
		ord[a[i]][ord[a[i]][0]++] = i;
	for (i = 0; i < t; ++i) {
		scanf("%d%d", &n, &k);
		if (k) {
			last = 0;
			if (n >= ord[k][ord[k][0]-1])
				printf("%d\n", ord[k][ord[k][0]-1]);
			else {
				search(1, ord[k][0]);
				printf("%d\n", last);
			}
		}
		else
			printf("1");
	}
	//end = clock();
	//printf("%d\n%d\n", nprimes, end - begin);
	return 0;
}