// Div Primi INFOAREAN

#include <fstream.h>

ifstream fin("divprim.in");
ofstream fout("divprim.out");
#define NMAX 1000005

int A[8][NMAX];

int main()
{
	int t,a,x; //Variabile folositoare
	fin>>t;
	int i,j; //Contori
	for (i=2;i<NMAX;i++)
	{
		if (A[0][i]==0)
			for (j = i; j< NMAX ; j+=i)
				A[0][j]++;
		for (j=1;j<=7;j++)
		{
			if (A[0][i]==j) A[j][i]=i;
			else
				A[j][i]=A[j][i-1];
		}
	}
	for (i=1;i<=t;i++)
	{
		fin>>a>>x;
//		int ok=0; // Var de control
		fout<<A[x][a]<<'\n';
	}
	fout.close();
	return 0;
}