#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int maxn = 1000001;
int ciur[maxn];
int ndiv[9][maxn];
int vlen[9];

void eratostene() {
    for (int i = 2; i < maxn; i++)
        if (!ciur[i]) {
            ciur[i]++;
            for (int j = i * 2; j < maxn; j += i)
                ciur[j]++;
        }
    for (int i = 2; i < maxn; i++)
        ndiv[ciur[i]][vlen[ciur[i]]++] = i;
}

void afis() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 10; j++)
            cout << ndiv[i][j] << ' ';
        cout << '\n';
    }
}

int main() {
    eratostene();
   // afis();
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int t;
    fin >> t;
    for (int tk = 0; tk < t; tk++) {
        int n, k;
        fin >> n >> k;
        int poz = lower_bound(ndiv[k], ndiv[k] + vlen[k], n) - ndiv[k];
        int val = ndiv[k][poz];
        if (val <= n)
            fout << val << '\n';
        else if (poz > 0 && ndiv[k][poz - 1] <= n)
            fout << ndiv[k][poz - 1] << '\n';
        else
            fout << "0\n";   
    }

    return 0;
}