#include<stdio.h>
#define N 1001

int n,t,kdiv[N],k,i,j;

void ciur()
{       int i,j;
        for(i=2;i*i<=N;i++)
		if(!kdiv[i])
                {       j=2;
                        kdiv[i]++;
                        while(i*j<=N)
                        {       kdiv[i*j]++;
                                j++;
                        }
                }
}
int main()
{       freopen("divprim.in","r",stdin);
        freopen("divprim.out","w",stdout);
	ciur();
        scanf("%d",&t);
	for(j=1;j<=t;j++)
        {       scanf("%d%d",&n,&k);
                for(i=n;i>=2;i--)
			if(kdiv[i]==k) {printf("%d\n",i);break;}
		if(i<2) printf("0\n");
	}
        return 0;
}