#include <bits/stdc++.h>
#define N 1000000
using namespace std;

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

int n, m;
int f[N + 1], a[8][N + 1], d[1000000];
int dim[] = { 0,0,0,0,0,0,0,0 };
bool c[N + 1];

void ciur()
{
    c[1] = 1;
    for (int i = 4; i <= N; i += 2)
        c[i] = 1;
    for (int i = 3; i * i <= N; i += 3)
        if (c[i] == 0)
            for (int j = i * i; j <= N; j += 2 * i)
                       c[j] = 1;
    for (int i = 1; i <= N; i++)
        if (c[i] == 0) d[++m] = i;
}

int cb(int k, int val)
{
    int st = 1, dr = dim[k], mij, rez = 0;
    while (st <= dr)
    {
        mij = st + (dr - st) / 2;
        if (a[k][mij] <= val) rez = a[k][mij], st = mij + 1;
        else dr = mij - 1;
    }
    return rez;
}

int main()
{
    ciur();
    for (int i = 1; i <= m; i++)
        for (int j = d[i]; j <= N; j += d[i])
            f[j]++;
    for (int i = 1; i <= N; i++)
        if (f[i] <= 7)
            a[f[i]][++dim[f[i]]] = i;
    int p, k;
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> p >> k;
        fout << cb(k, p) << '\n';
    }
    fin.close(); fout.close();
    return 0;
}