#include<stdio.h>
#define MAX 1000001
long long v[MAX][8],n,t,k;
void ciur()
{
	int i,j;
	for(i=2;i<=MAX;++i)
	{
		if(!v[i][0])
		{v[i][0]=1;
		for(j=i+i;j<=MAX;j+=i)
		++v[j][0];
		}
		v[i][v[i][0]]=i;
		for(j=1;j<8;++j)
		if(!v[i][j])
			v[i][j]=v[i-1][j];
	}
}
int main()
{
	ciur();
	FILE*f=fopen("divprim.in","r");
	fscanf(f,"%lld",&t);	
	FILE*g=fopen("divprim.out","w");
	for(;t;--t)
	{
		fscanf(f,"%lld%lld",&n,&k);
		if(v[n][k])fprintf(g,"%lld\n",v[n][k]);
		else fprintf(g,"0\n");
	}
	fclose(f);
	fclose(g);
	return 0;
}