#include<stdio.h>
#define NMAX	100000UL
//#define k7	2*3*5*7*11*13*17       // 510510

int main()
{
unsigned long t,n[NMAX]={0},k[NMAX]={0},i,j,d,p,cmmn=1,pr[3500]={0},nrp;
unsigned long min[8]={1,2,6,30,210,2310,30030,510510},y,cy,nrdiv,gata;
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
scanf("%lu",&t);
for(i=0;i<t;i++)
	scanf("%lu%lu",&n[i],&k[i]);
pr[0]=1;
pr[1]=2;
nrp=2UL;
for(i=3;i<=1010;i=i+2){
	p=1;
	for(d=1;pr[d]*pr[d]<=i;d++)
		if(i%pr[d]==0) {p=0;break;}
	if(p) {pr[nrp]=i;nrp++;}
	}


for(i=0;i<t;i++){
	if(n[i]==1) cmmn=min[0];
	else{
		switch (k[i]){
			case 0:cmmn=min[0];break;
			case 7:if (n[i]>=min[7]) cmmn=min[7];
				   else cmmn=0; break;
			default:
				y=n[i];gata=0;
				while(!gata&&y>=min[k[i]]){
					nrdiv=0;
					cy=y;
					d=1;
					while(cy>1){
						if(cy%pr[d]==0){
							nrdiv++;
							while(cy%pr[d]==0) cy/=pr[d];
							}
						d++;
						}
					if(nrdiv==k[i]) gata=1;
					else y--;
					}
				if(!gata) cmmn=0;
				else cmmn=y;
			}
		}
	printf("%lu\n",cmmn);
	}



return 0;
}