#include <iostream>
#include <fstream>
#include <algorithm>
#define dMAX 1000000

using namespace std;

int Q, n, k, c, result;

struct Element{
    unsigned int number;
    unsigned short int frecv;
} sieve[dMAX];

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

bool Compare(Element e1, Element e2) {
    if (e1.frecv == e2.frecv) return e1.number < e2.number;
    return e1.frecv < e2.frecv;
}

void BinarySearch(int a, int b) {
    if (a > b) return;
    c = a + (b - a) / 2;
    if (sieve[c].frecv == k) {
    if (sieve[c].number <= n) {
        result = sieve[c].number;
        BinarySearch(c + 1, b);
    } else
        BinarySearch(a, c - 1);
    } else {
        if (sieve[c].frecv > k) {
            BinarySearch(a, c - 1);
        } else {
            BinarySearch(c + 1, b);
        }
    }
}

int main()
{
    int i, j;
    fin >> Q;
    sieve[0].frecv = sieve[1].frecv = 1;
    sieve[1].number = 1;
    sieve[0].number = 0;
    for (i = 2; i < dMAX; i++) {
        sieve[i].number = i;
        if (sieve[i].frecv == 0) {
            for (j = i + i; j < dMAX; j += i) {
                sieve[j].frecv++;
            }
        }
    }
    //sort(sieve, sieve + dMAX, Compare);

    /*for (i = 1; i <= Q; i++) {
        fin >> n >> k;
        BinarySearch(1, dMAX);
        fout << result << "\n";
        result = 0;
    }/*
    return 0;
}