#include<fstream>
#include<iostream>
using namespace std;
#define n 1000005
int w[n],a[n][8];
int main()
{
	int i,j,k,u;
	ifstream fcin("divprim.in");
	ofstream fcout("divprim.out");
	for(i=2;i<=n;i++)
		if(w[i]==0)
			for(j=i;j<=n;j+=i)
				w[j]++;
	for(k=1;k<=7;k++)
	{
		u=0;
		for(i=2;i<=n;i++)
			if(w[i]==k)
			{
				a[i][k]=i;
				u=i;
			}
			else
				a[i][k]=u;
	}
	fcin>>j;
	while(j--)
	{
		fcin>>i>>k;
		fcout<<a[i][k]<<"\n";
	}		
	return 0;
}