#include<stdio.h>
int v[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int main()
{
	long t,n,k,i,j,a,b;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%ld",&t);
	for(i=0;i<t;i++)
	{scanf("%ld%ld",&n,&k);
	a=1;
	if(k=0) printf("%ld",1);
	else
	{
		for(j=0;j<k;j++)
			a*=v[j];
		b=(n/a)*a;
		printf("%ld",b);
	}}
	return 0;
}