#include<stdio.h>
using namespace std;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,k,n,nrdiv,d,exp,cp;bool ok;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		scanf("%d%d",&n,&k);
		for(int j=n;j>=1;j--){
			nrdiv=0;ok=0;d=2;cp=j;
			do{
				exp=0;
				while(cp%d==0){cp/=d;exp++;}
				if(exp!=0) nrdiv++;
				d++;
			}while(cp!=1);
			if(nrdiv==k){printf("%d",j);ok=1;break;}
		}
	if(!ok)	printf("0");
	}
	return 0;
}