#include <cstdio>

char a[1000000]; 

int nrfact(int y) //afla numarul de divizori primi
{
	int nr;
    for (int i=2;i*i<=y;i++)
	{
		nr=0;
		if (y%i==0)
		{
			nr++;
			while (y%i==0)
				y=y/i;
		}
	}
	if (y!=1) nr++;
	return nr;
}

/*
int cautbin()
{
	int i,pas=1<<20;
    for (i=0;pas;pas>>=1) // pas=pas/2;
        if (a[i])
            i=i+pas;
    return i+1;
}
*/

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,n,k,i,j;
	scanf("%d",&t);
	for (i=1;i<=1000000;i++)
		a[i]=nrfact(i);
	for (i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		for (j=n;j>0;j--)
			if (a[j]==k) 
			{
				printf("%d\n",j);
				break;
			}
		if (j==0) printf("0\n");
	}
	return 0;
}