#include <stdio.h>
#include <string.h>
FILE *f, *g;
long k, s[1500], i, j, t, h, l, n, x, o;

void ciur(void)
	{
	int v[10001], i;
	memset(v, 0, sizeof(v));
	s[1]=2;
	k=1;
	for (i=3;i<=10000;i+=2)
		if (!v[i])
			{
			s[++k]=i;
			for (j=i;j*i<=10000;j++)
				v[i*j]=1;
			}
	}

int main(void)
{
f=fopen("divprim.in", "r");
g=fopen("divprim.out", "w");
fscanf (f, "%ld", &x);
ciur();
for (i=1;i<=x;i++)
	{
	fscanf(f, "%ld%ld", &n, &o);
	for (j=n;j>=4;j--)
		{
		t=j;
		l=0;
		for (h=1;h<=k;h++)
			if (t%s[h]==0)
				{
				l++;
				t/=s[h];
				while (t%s[h]==0)
					t/=s[h];
				if (t==1)
					break;
				}
		if (l==o)
			break;
		}
	if (j!=3)
		fprintf(g, "%ld\n", j);
	else
		fprintf(g, "0\n");
	}
fcloseall();
return 0;
}