#include <bits/stdc++.h>
#define nmax 1000001

using namespace std;

int n, k, t[nmax];
int a[nmax][8]; /// a[i][j] = numarul maxim din intervalul[1..i] care are
                /// exact j divizori primi
void Ciur()
{
    int i, j;
    for(i = 2; i < nmax; i += 2)
        t[i] = 1;
    for(i = 3; i < nmax; i += 2)
        if(t[i] == 0)
            for(j = i; j < nmax; j += i)
                t[j]++;
}

int main()
{
    int i, j, T, pas;
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    Ciur();
    for(i = 1; i < nmax; ++i)
        for(j = 0; j < 8; ++j)
            if(t[i] == j) a[i][j] = i;
            else a[i][j]=a[i - 1][j];
    fin >> T;
    for (pas = 1; pas <= T; ++pas)
    {
        fin >> n >> k;
        fout << a[n][k] <<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}