// Divprim.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <cstdio>
#define N 1000001
#define K 8

using namespace std;


FILE *f=fopen("divprim.in", "r");
FILE *g=fopen("divprim.out", "w");

int count[1000001];
int max[8][1000001];
int t;


void program()
{
	int i, j;
	for (i=2; i<N; i+=2)
		count[i]=1;
	for (i=3; i<N; i+=2)
		if (count[i]==0)
			for (int j=i; j<N; j+=i)
				count[j]++;


	for (i=1; i<N; i++)
		for (int j=0; j<K; j++)
			if (count[i]==j)
				max[j][i]=i;
			else
				max[j][i]=max[j][i-1];
}


int main()
{
	program();
	fscanf(f, "%d", &t);
	for (int i=1; i<=t; ++i)
	{
		int x, k;
		fscanf(f, "%d%d", &x, &k);
		fprintf(g, "%d\n", max[k][x]);
	}
	fclose(f);
	fclose(g);
	return 0;
}