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

int main()
{
int t,i,d,p,cmmn=1,pr[200]={0},nrp,n,k;
int min[8]={1,2,6,30,210,2310,30030,510510},y,cy,nrdiv,gata;
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);

pr[0]=1;
pr[1]=2;
nrp=2;
for(i=3;i<=1001;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++;}
	}
scanf("%d",&t);

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



return 0;
}