#include <fstream>

using namespace std;
const int NMAX = 1000000;
unsigned char nDiv[NMAX + 1];
int M[NMAX + 1][8];
ifstream f("divprim.in");
ofstream g("divprim.out");
void ciur(int n)
{
    int i, j;
    for(i = 2; i <= n; i += 2)
        nDiv[i] = 1;
    for(i = 3; i <= n; i += 2)
    {
        if(nDiv[i] == 0)
        {
            for(j = i; j <= n; j += i)
                nDiv[j]++;
        }
    }
}
void precalcul(int n)
{
    for(int i = 1; i <= n; i++)
    {
        for(int k = 0; k <= 7; k++)
            M[i][k] = M[i - 1][k];
        M[i][nDiv[i]] = i;
    }
}
int main()
{
    int T, N, K;
    ciur(NMAX);
    precalcul(NMAX);
    f >> T;
    while(T--)
    {
        f >> N >> K;
        g << M[N][K] << '\n';
    }
    return 0;
}