#include <stdio.h>
int t,n,k,k1,l,e,i,d,j,j1,v,g;
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
		scanf("%d %d",&n,&k);
		g=0;
		for(j=n;j>1;j--)
		     {
				j1=j;
				d=2;
				e=0;
				k1=0;
				while(j1>1)
				{
				   e=0;
				   v=1;
				   while(j1%d==0)
				   {
						 e++;
						 j1=j1/d;
						 v=0;
				   }
				   d++;
				 if(v==0)
				    k1++;
				}

				if(k1==k)
				{
				    printf("%d\n",j);
				    g=1;
				break;
				}
		     }
		if(g==0) printf("%d\n",0);
    }
    return 0;
}