#include <stdio.h>
#define max 100001
#define T 100000   
int pr[150000],k=0;  
int e[max];
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[++k]=i;   
}   
void precalcul()
{
	int i,j;
	for (i=1; i<max; i++)
	{
		for (j=1; pr[j]<=i; j++)
			if (i%pr[j]==0)
				e[i]++;
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,i,n,k,j,gasit;
	scanf("%d",&t);
	ciur();
	precalcul();
	for (i=1; i<=t; i++)
	{
		gasit=0;
		scanf("%d%d",&n,&k);
		for (j=n-1; j>=1; j--)
			if (e[j]==k)
			{
				printf("%d\n",j);
				break;
				gasit=1;
			}
		if (gasit==0)
			printf("0\n");
	}
	return 0;
}