#include <fstream>
#include <vector>
#include <iostream>
#define MAX 1000001
#define MAX_PRIME 150000

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

bool v[MAX];
int p[MAX_PRIME], nrdiv[MAX] = {0};
vector<int> tmp[8];

int sieve(int n) {
	long long i,j;
	int k = 0;

	p[k++] = 2;
	for(i = 3; i < n; i += 2)
		if(!v[i]) {
			p[k++] = i;
			for(j = i*i; j <= n; j += i)
				v[j] = true;
		}
	return k;
}

int binary_search(int val, vector<int> &A)
{
    unsigned int i, step;
    for (step = 1; step < A.size(); step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < A.size() && A[i + step] <= val)
           i += step;
    return i;
}

int main() {
	int T,K,N,i,j,primes,nr;

	primes = sieve(MAX-1);

	for(i = 0; i < primes; i++)
		for(j = p[i]; j < MAX; j += p[i])
			nrdiv[j]++;

	for(i = 0; i < MAX; i++) {
		tmp[nrdiv[i]].push_back(i);
	}

	f>>T;
	for(i = 0; i < T; i++) {
		f>>N>>K;

		nr = binary_search(N,tmp[K]);
		if(tmp[K][nr] <= N)
			g<<tmp[K][nr]<<"\n";
		else
			g<<0<<"\n";
	}

	return 0;
}