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

int main()
{
int t,n[NMAX]={0},k[NMAX]={0},i,d,p,cmmn=1,pr[3500]={0},nrp;
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);
scanf("%d",&t);
for(i=0;i<t;i++)
	scanf("%d%d",&n[i],&k[i]);
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++;}
	}


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



return 0;
}