#include <fstream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

const int Max = 1e6;

int ciur[Max + 5];

vector <int> prime[8];

int t;

void ciurul()
{
    for (int i = 2; i <= Max; i += 2) {
        ciur[i] = 1;
    }

    for (int i = 3; i <= Max; i += 2) {
        if (!ciur[i]) {
            for (int j = i; j <= Max; j += i) {
                ++ciur[j];
            }
        }
    }

    for (int i = 1; i <= Max; ++i) {
        prime[ciur[i]].push_back(i);
    }
}

int cautareBinara(int n, int k)
{
    if (prime[k][0] > n) {
        return 0;
    }
    else {
        return (prime[k][upper_bound(prime[k].begin(), prime[k].end(), n) - prime[k].begin() - 1]);
    }
}

int main() {
    ciurul();

    f >> t;

    while(t--) {
        int n, k;
        f >> n >> k;

        g << cautareBinara(n, k) << '\n';
    }

    return 0;
}