#include <fstream>
#include <bitset>

using namespace std;

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

const int MAXN = 1e6 + 5;

bitset < MAXN > ciur;
int P[MAXN >> 1],K;
int v[MAXN];

void sieve()
{
    ciur[0] = ciur[1] = 1;
    for (int i = 2; i < MAXN; ++i)
    {
        if (!ciur[i])
        {
            P[++K] = i;
            for (int j = (i << 1); j < MAXN; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
}

int main()
{
    int t,i,j,x,k;
    sieve();
    for (i = 1; i <= K; ++i)
    {
        for (j = P[i]; j < MAXN; j += P[i])
        {
            ++v[j];
        }
    }
    fin >> t;
    while (t--)
    {
        fin >> x >> k;
        bool ok = 0;
        for (i = x - 1; i >= 2; --i)
        {
            if (v[i] == k)
            {
                fout << i << '\n';
                ok = 1;
                break;
            }
        }
        if (!ok) fout << 0 << '\n';
    }
    return 0;
}