#include <fstream>
#include <cstdio>
#include <cmath>
using namespace std;

// DOH! the last solution was good for another problem (,*)[

const int NMAX = 1000001, KMAX = 7, PMAX = 78499;
int primes[PMAX], dp[KMAX][NMAX] = {};
char comp[(NMAX >> 4) + 3];

inline bool prchk(int k)
{ return !(comp[k >> 3] & (1 << (k & 7))); }

void erathos()
{
    int K = 1, N, n, i, j;
    primes[1] = 2;
    N = (int)sqrt(NMAX) >> 1;
    n = NMAX >> 1;
    ++N;
    for (i = 1; i != N; ++i)
        if ( prchk(i) ) {
            primes[++K] = (i << 1) + 1;
            for (j = i * (i + 1) << 1; j <= n; j += (i << 1) + 1)
                comp[j >> 3] |= 1 << (j & 7);
        }
    for (; i != n; ++i)
        if ( prchk(i) )
            primes[++K] = (i << 1) + 1;
    primes[0] = K;
}

void gen_numbers()
{
    int i, j, divp[NMAX] = {}, t;
    erathos();
    for (i = 2; i != NMAX; ++i) {
        if ( !(i & 1) ) divp[i] = divp[i >> 1] + (bool)(i & 2);
        else if ( prchk(i >> 1) ) divp[i] = 1;
        else {
            for (j = 2; j != PMAX; ++j)
                if ( !(i % primes[j]) ) {
                    t = i / primes[j];
                    divp[i] = divp[t];
                    divp[i] += (bool)(t % primes[j]);
                    break;
                }
        }
        for (j = 0; j != KMAX; ++j)
            dp[j][i] = dp[j][i - 1];
        dp[ divp[i] - 1 ][i] = i;
    }

}

// So, shall we implement a BS or interpolation?
int search(int k, int q)
{
    int *x = dp[k];
    int L = x[0], step, i;
    // let's go with BS
    for (step = 1; step <= L; step <<= 1);
    for (i = 0; step; step >>= 1) {
        if ((i | step) <= L)
            if (x[i | step] <= q) i |= step;
    }
    if (i) return x[i];
    else return 0;
}

int main()
{
    int T, t, N, K;
	gen_numbers();
    ifstream fin("divprim.in");
    freopen("divprim.out", "w", stdout);
    fin >> T;
    for (t = 0; t != T; ++t) {
        fin >> N >> K;
        if (K == 0) printf("1\n");
        else printf("%d\n", dp[K - 1][N]);
    }
    
	
	return 0;
}