#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#define NMAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int nrdiv[NMAX];
int dp[8][NMAX];

int main() {
	int q,i,j,n,k;

	fin>>q;

	for(i=2;i<NMAX;++i)
		if(nrdiv[i]==0)
			for(j=i;j<NMAX;j+=i)
				++nrdiv[j];

	for(i=1;i<8;++i)
		for(j=1;j<NMAX;++j)
			if(nrdiv[j] == i) dp[i][j]=j;
			else dp[i][j]=dp[i][j-1];

	while(q--) {
		fin>>n>>k;
		fout<<dp[k][n]<<'\n';
	}

	return 0;
}