#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define dMAX 1000002

using namespace std;

int Q, sieve[dMAX], n, k, temp;
int a, b, c, result;
vector<int> L[9];

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main()
{
    int i, j;
    fin >> Q;
    sieve[0] = sieve[1] = 0;
    for (i = 2; i <= 1000000; i++) {
        if (sieve[i] == 0) {
            for (j = 2; j <= 1000000/i; j++) {
                sieve[i * j]++;
            }
            sieve[i] = 1;
        }
    }
    for (i = 0; i <= 1000000; i++) {
        L[sieve[i]].push_back(i);
    }
    for (; Q--; ) {
        fin >> n >> k;
        a = 0, b = L[k].size() - 1;
        result = -1;
        while (a <= b) {
            c = a + (b - a) / 2;
            if (L[k][c] <= n) {
                result = c;
                a = c + 1;
            } else b = c - 1;
        }
        if (result == -1) fout << "0\n";
        else fout << L[k][result] << "\n";
    }
    return 0;
}