#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int NMAX = 1000000; // corect: 1e6
bitset<NMAX + 5> is_prime;

void ciur() {
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (int i = 4; i <= NMAX; i += 2)
        is_prime[i] = 0;
    for (int i = 3; i * i <= NMAX; i += 2)
        if (is_prime[i])
            for (int j = i * i; j <= NMAX; j += i)
                is_prime[j] = 0;
}

int cnt[1000005];
vector<int> tt[8];

void precalc() {
    for (int i = 2; i <= NMAX; i++) {
        if (is_prime[i]) {
            for (int j = i; j <= NMAX; j += i)
                cnt[j]++;
        }
    }
    for (int i = 1; i <= NMAX; i++) {
        int k = cnt[i];
        if (k <= 7) tt[k].push_back(i);
    }
}

struct sett {
    int maxi;
    int div;
};

sett v[100001];

int main() {
    ciur();
    precalc();
    int t;
    fin >> t;
    for (int i = 1; i <= t; i++) {
        fin >> v[i].maxi >> v[i].div;
        int k = v[i].div;
        if (k > 7 || k < 0 || tt[k].empty()) {
            fout << 0 << '\n';
            continue;
        }
        auto it = upper_bound(tt[k].begin(), tt[k].end(), v[i].maxi);
        if (it == tt[k].begin()) fout << 0 << '\n';
        else {
            --it;
            fout << *it << '\n';
        }
    }
}