#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>

long int prime[1000000],t,n;
int v[1000000],k;

int divprim(int nr){
	int ko=0;
	for(int i=1;prime[i]<=nr/2;i++)
		if(nr % prime[i] == 0) ko++;
	return ko;


}

int main(){
	int i;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);

	scanf("%d",&t);
	for(int o=1;o<=t;o++){
		scanf("%ld %d",&n,&k);

		for(i=2;i<=n;i++){
			if(v[i]==0){
				for(int j=2;j<=n;j++)
					v[j*i]=1;

				}	               // gen n numere prime

			}
		int p=1;
		for(i=2;i<=n;i++)
			if(v[i]==0) { prime[p]=i; p++;}

		int kk=1;
		for(int j=n;j>=1;j--)
			if(divprim(j)==k){
				printf("%d",j);
				kk=0;
				break;
				}
		if(kk==1) printf("0");

		}

return 0;
}