#include <fstream>

using namespace std;
int v[1000001],m[8][1000001];
int main()
{
	ifstream cin("divprim.in");
	ofstream cout("divprim.out");

    int n,k,i,j,t;

    for(i=2;i<1000001;i++)
    {
		if(v[i]==0)
		{
			for(j=i;j<1000001;j+=i)
			{
				v[j]++;
			}
		}

		for(j=1;j<8;j++)
		{
			m[j][i]=m[j][i-1];
		}

		if(v[i]<8)
		{
			m[v[i]][i]=i;
		}
    }

    cin>>t;
    for(i=0;i<t;i++)
    {
		cin>>n>>k;
		cout<<m[k][n]<<'\n';
    }

    return 0;
}