#include <fstream>

using namespace std;

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

int ciur[1000100], i, j, t, n, k, pr, lin;
int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19};
int nrd[8][1000100], l, r, m, x, sol;

int main()
{
    ciur[1] = 0;
    ciur[2] = 1;
    for (i = 4; i <= 1000000; i += 2)
        ciur[i]++;
    for (i = 3; i <= 1000000; i += 2) {
        if (ciur[i] == 0) {
            ciur[i] = 1;
            for (j = i * 2; j <= 1000000; j += i)
                ciur[j]++;
        }
    }
    for (i = 2; i <= 1000000; i++) {
        if (ciur[i] <= 7) {
            lin = ciur[i];
            nrd[lin][0]++;
            nrd[lin][nrd[lin][0]] = i;
        }
    }
    f >> t;
    for (i = 1; i <= t; i++) {
        f >> n >> k;
        if (k == 0)
            g << 1;
        else {
            pr = 1;
            for (j = 1; j <= k; j++)
                pr *= prime[j];
            if (pr > n)
                g << 0;
            else {
                lin = k;
                l = 1;
                r = nrd[lin][0];
                while (l <= r) {
                    m = (l + r) / 2;
                    x = nrd[lin][m];
                    if (x > n)
                        r = m - 1;
                    else {
                        sol = x;
                        l = m + 1;
                    }
                }
                g << sol;
            }
        }
        g << '\n';
    }
    f.close();
    g.close();
    return 0;
}