#include <bits/stdc++.h>

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int T, N, K, pr[1000010],D[1000010][20], nr[20], s, d;
int main()
{
    pr[0] = pr[1] = 1;
    for(int i = 2;i <= 1000000;i++)
    {
        if(pr[i] == 0)
            for(int j = 1;j * i <= 1000000;j++)
                pr[j * i]++;
    }
    for(int i = 1;i<= 1000010;i++)
    {
        nr[pr[i]]++;
        D[nr[pr[i]]][pr[i]] = i;
    }
    in >> T;
    for(int i = 1;i <= T;i++)
    {
        in >> N >> K;
        s = 0;
        d = nr[K];
        while(d - s > 1)
        {
            int mij = s + (d - s) / 2;
            if(D[mij][K] >= N) d = mij;
            else s = mij;
        }
        out << D[s][K] << '\n';
    }
    return 0;
}