#include <fstream>

using namespace std;

const int NMAX = 1e6 + 5;

ifstream cin ("divprim.in");
ofstream cout ("divprim.out");

char divv[NMAX];
int d[NMAX][10];
void Precalc(int n)
{
    for(int i = 2; i <= n; i += 2) {
        divv[i] = 1;
    }
    for(int i = 3; i <= n; i += 2)
        if(divv[i] == 0)
            for(int j = i; j <= n; j += i)
                divv[j]++;
    d[1][0] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 0; j <= 7; ++j)
            d[i][j] = d[i - 1][j];
        d[i][divv[i]] = i;
    }
}

int main() {
    Precalc(1e6);
    int t;
    cin >> t;
    for(int i = 1; i <= t; ++i) {
        int n, k;
        cin >> n >> k;
        cout << (int)d[n][k] << "\n";
    }
    return 0;
}