#include <stdio.h>
#include <vector>
#define N 2000200
using namespace std;

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int i,j,nr,n,p=1,numere=0,t,k,l,div,q,gasit;
	int a[N];
	scanf("%d",&t);
	for (l=1; l<=t; l++)
	{
		div=0;
		gasit=0;
	scanf("%d %d",&n,&k);
	nr=0;
	vector <bool> c(N,false);
	for (i=2; i*i<=n; ++i)
	{
		if (c[i]==false)
            for (j=i*i; j<=n; j=j+i)
                c[j]=true;				
	}
	for (i=2; i<=n; ++i)
	{
		if (!c[i]) 
		{
			a[p]=i;
			p++;
			numere++;
		}
	}
	for (q=n-1; q>=1 && gasit=0; q--)
	{
		for (p=1; p<=numere; p++)
		if (q%a[p]==0)
			div++;
		if (div==k)
		{
			gasit=1;
			printf("%d",q);
		}
	}
	}
	return 0;
}