#include <stdio.h>
#define DIM 1000010

int nrPrime[DIM], nrDivPrim[DIM], sol[8][DIM];

void erathostene(int n) {
	int i, j;
	nrPrime[0]=nrPrime[1]=1;
	for (i=2; i*i <= n; ++i)
	  if (!nrPrime[i])
		for (j=2; i*j<=n; ++j)
			nrPrime[i*j]=1, nrDivPrim[i*j]++;
}

int search (int n, int k) {
	int left=1, right=sol[k][0], mid;

	while (left<=right) {
		mid=(left+right)/2;
		if (sol[k][mid]<=n && n<sol[k][mid+1])
			return mid;
		else if (sol[k][mid]<n) left=mid+1;
		else if (sol[k][mid]>n) right=mid-1;
	}
	return 1;
}


int main() {
	int T, n, k, i;

	erathostene(DIM-1);

	FILE *f=fopen ("divprim.in", "r");
	FILE *g=fopen ("divprim.out", "w");
	fscanf(f, "%d", &T);

	for (i=1; i<=7; ++i) sol[i][0]=1;
	sol[0][0]=2; sol[0][2]=1;

	for (i=2; i<DIM; ++i)
		if (nrDivPrim[i]==0)
			sol[ 1 ][ ++sol[1][0] ] = i;
		else sol[ nrDivPrim[i] ][ ++sol[nrDivPrim[i]][0] ] = i;
	for (i=0; i<=7; ++i) sol[i][sol[i][0]+1]=DIM-1;
	while (T--) {
		fscanf(f, "%d %d", &n, &k);
		i=search (n, k);
		//i=sol[k][0];
		//while (sol[k][i]>n) i--;
		fprintf(g, "%d\n", sol[k][i]);
	}
	fclose(f);
	fclose(g);
	return 0;
}