#include <bits/stdc++.h>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
const int CIURMAX = 1000000;
const int CNT = 379750;
bool not_prime[CIURMAX + 5];
int fr[CIURMAX + 5];
int cnt[8], a[8][CNT];
void ciur()
{
    not_prime[0] = not_prime[1] = 1;
    fr[2] = 1;
    for (int i = 4; i <= CIURMAX; i += 2)
        not_prime[i] = 1, fr[i]++;
    for (int i = 3; i <= CIURMAX; i += 2)
        if (not_prime[i] == 0)
            for (int j = i; j <= CIURMAX; j += i)
                not_prime[j] = 1, fr[j]++;

    /*
    // aflu cate numere au i factori primi cu i de la 0 la 7
    int cnt[8] = {};
    for (int i = 0; i <= CIURMAX; i++)
        if (fr[i] <= 7)
            cnt[fr[i]]++;
    for (int i = 0; i <= 7; i++)
        cout << cnt[i] << ' ';
    // 2 78734 288726 379720 208034 42492 2285 8
    */

    for (int i = 1; i <= CIURMAX; i++)
        if (fr[i] <= 7)
            a[fr[i]][++cnt[fr[i]]] = i;
}
int main()
{
    ciur();
    int T;
    f >> T;
    for (int t = 1; t <= T; t++)
    {
        int n, k;
        f >> n >> k;
        auto it = upper_bound(a[k], a[k] + cnt[k], n);
        if (*it == a[k][0])
            g << 0 << '\n';
        {
            it--;
            g << *it << '\n';
        }
    }
    return 0;
}