#include<fstream>
#include<vector>
#include<stdio.h>
using namespace std;
int v[1000002];
int haha[8][1000001],k[8];
void ciur()
{
	int i,j;
	for(i=2;i<=1000000;i++)
	{
		if(v[i]==0)
		{   
			for(j=1;j*i<=1000000;j++)
				v[j*i]++;
		}
		haha[v[i]][++k[v[i]]]=i;
	}
}
int cautare_binara(int i,int x,int lungime)
{
	int j,pas;
	for(pas=1;pas<lungime;pas<<=1);
		for(j=0;pas;pas>>=1)
			if(j+pas<lungime&&haha[i][j+pas]<=x)
				j+=pas;
	return j;
}
int main()
{
	freopen ("divprim.in","r",stdin);
	freopen ("divprim.out","w",stdout);
	int poz,i,N,K,T;
	ciur();
	haha[0][1]=1;
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%d%d",&N,&K);
		poz=cautare_binara(K,N,k[K]);
		if(haha[K][poz]<=N)
			printf("%d\n",haha[K][poz]);
		else
			printf("%d\n",haha[K][--poz]);
	}
	return 0;
}