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

void afla(void)
	{
	long i, j, t;
	memset(v, 0, sizeof(v));
	for (i=4;i<=u;i++)
		{
		t=i;
		for (j=1;j<=k&&t!=1;j++)
			{
			if (s[j]>i/2)
				break;
			if (i%s[j]==0)
				{
				v[i]++;
				t/=s[j];
				while (t%s[j]==0)
					t/=s[j];
				}
			}
		}
	}
void ciur(void)
	{
	int i;
	memset(v, 0, sizeof(v));
	s[1]=2;
	k=1;
	for (i=3;i<=u;i+=2)
		if (!v[i])
			{
			s[++k]=i;
			for (j=i;j*i<=u;j++)
				v[i*j]=1;
			}
	}

int main(void)
{
f=fopen("divprim.in", "r");
g=fopen("divprim.out", "w");
fscanf (f, "%ld", &x);
ciur();
afla();
for (i=1;i<=x;i++)
	{
	fscanf(f, "%ld%ld", &n, &o);
	for (j=n;j>=4;j--)
		if (v[j]==o)
			{
			fprintf(g, "%ld\n", j);
			break;
			}
	if (j<4)
		fprintf(g, "0\n");
	}
fcloseall();
return 0;
}