#include <stdio.h>

#define MAX 1000000

long int ciur[MAX];
long int i, j, k, n;
int p, gasit;
int t, nr;

int main()
{
	FILE *f = fopen ("divprim.in","r");
	FILE *g = fopen ("divprim.out","w");
	fscanf (f,"%d", &t);
	
	for (i=2; i<MAX; ++i)
		ciur[i] = 1;
	for (i=2; i*i < MAX; ++i)
		if (ciur[i])
			for (j=2; j*i < MAX; ++j)
				ciur[i*j] = 0;
	
	
	for (i=1; i<=t; ++i)
	{
		fscanf (f,"%ld %ld", &n, &k);
		j = n - 1;
		while (j > 1)
		{
			nr = 0;
			for (p=j; p>=2; --p)
			{
				if (ciur[p] && j % p == 0)
					nr ++;
				if (nr > k)
					break;
			}
			if (nr == k)
			{
				fprintf (g,"%ld\n", j);
				gasit = 1;
				break;
			}
			j --;
		}
		if (j == 1)
			fprintf (g,"0\n");
	}
	
	fclose(g);
	fclose(f);
	return 0;
}