#include <stdio.h>
#define T 45000   
int pr[45000],h=0;   
void ciur()   
{   
    int i,j;   
    bool c[T]={false};   
    for (i=2; i*i<T; i++)   
    {   
        if (!c[i])   
            for (j=i*i; j<T; j+=i)   
                c[j]=true;   
    }   
    for (i=2; i<T; ++i)   
        if (!c[i])   
            pr[++h]=i;   
}   
int div(int n, int k)
{
	int i,j,nrpr=0;
	for (i=1; pr[i]<=n; i++)
		if (n%pr[i]==0)
			nrpr++;
	if (nrpr==k)
		return true;
	else
		return false;
}
	
int divprim(int n,int k)
{
	int i,j;
	for (j=n-1; j>=1; j--)
		if (div(j,k)==true)
			return j;
	return 0;
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,n,k,i;
	scanf("%d",&t);
	ciur();
	for (i=1; i<=t; i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",divprim(n,k));
	}
	return 0;
}