#include <fstream>

using namespace std;

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

int ciur[1000100], i, j, t, n, k, pr;
int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19};

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]++;
        }
    }
    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 {
                for (j = n; j >= pr; j--) {
                    if (ciur[j] == k) {
                        g << j;
                        j = 1;
                    }
                }
            }
        }
        g << '\n';
    }
    f.close();
    g.close();
    return 0;
}