#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int MAX_K = 7;

vector <int> primes[MAX_K + 1];
int step[MAX_K + 1];

unsigned char p[MAX_N + 1];

inline int primeDivCnt(int x)
{
    bool add = !(x & 1);
    while (!(x & 1))
        x >>= 1;
    return p[x] + add;
}

void sieve()
{
    for (int i = 3; i <= MAX_N; i += 2)
    {
        if (!p[i])
            p[i] = 1;
        for (int j = (i << 1) + i; j <= MAX_N; j += (i << 1))
            p[j]++;
    }
    for (int i = 2; i <= MAX_N; i++)
    {
        if (primeDivCnt(i) <= MAX_K)
            primes[primeDivCnt(i)].emplace_back(i);
    }
    for (int i = 1; i <= MAX_K; i++)
        step[i] = (1 << (30 - __builtin_clz((int) primes[i].size())));
}

int main()
{
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    ios_base::sync_with_stdio(0);
    in.tie(0);
    int T;
    int n, k;
    int pos;

    sieve();

    in >> T;
    while (T--)
    {
        in >> n >> k;

        if (k <= 0)
        {
            out << "1\n";
            continue;
        }

        pos = 0;
        for (int s = step[k]; s; s >>= 1)
        {
            if (pos + s < (int) primes[k].size() && primes[k][pos + s] <= n)
                pos += s;
        }
        if (primes[k][pos] <= n)
            out << primes[k][pos] << '\n';
        else
            out << "0\n";
    }
    in.close();
    out.close();
    return 0;
}