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



return 0;
}