#include <fstream>
#include <vector>
using namespace std;

const string FILE_NAME = "divprim";
const int VAL_MAX { 1000005 };

ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };

int N, K;
vector<int> ciur(VAL_MAX);
vector< vector<int> > d(10);

int main() {
    ios_base::sync_with_stdio(false);
    in.tie(0);
    out.tie(0);
    
    for (int i { 2 }; i < VAL_MAX; ++i)
        if (!ciur[i])
            for (int j { i }; j < VAL_MAX; j += i)
                ++ciur[j];
    
    d[0].push_back(1);
    for (int i { 1 }; i < VAL_MAX; ++i)
        if (ciur[i] <= 7)
            d[ciur[i]].push_back(i);
    
    int t;
    in >> t;
    while (t--) {
        in >> N >> K;
        
        auto it = lower_bound(d[K].begin(), d[K].end(), N);
        if (it == d[K].end())
            out << d[K].back() << '\n';
        else if (*it == N)
            out << *it << '\n';
        else if (it == d[K].begin())
            out << 0 << '\n';
        else
            out << *(it - 1) << '\n';
    }
}