#include <fstream>

#define LIM 1000005

using namespace std;

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

int t;

int n, k;

int v[LIM];

int dp[LIM][8];

int main()
{
    for (register int i=2; i<=LIM; ++i)
        if ( v[i] == 0 )
            for (register int j=0; j<=LIM; j+=i)
                ++v[j];
    for (register int i=1; i<=LIM; ++i)
    {
        for (register int j=0; j<=7; ++j)
            dp[i][j] = dp[i-1][j];
        if ( v[i] <= 7 )
            dp[i][v[i]] = i;
    }
    in >> t;
    for (register int q=1; q<=t; ++q)
    {
        in >> n >> k;
        out << dp[n][k] << '\n';
    }
    return 0;
}