#include <fstream>

using namespace std;

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

const int N = 1000001;
int v[N], m[N][8];

int main()
{
    int i,j;
    for(i=2;i<=N;i++)
    {
        if(v[i]==0)
        {
            for(j=1; i*j<=N; j++)
            {
                v[i*j]++;
            }
        }
    }
    for(i=2;i<=N;i++)
    {
        for(j=1;j<=7;j++)
        {
            m[i][j]=m[i-1][j];
        }
        m[i][v[i]]=i;
    }

    int T, n, k;
    in >> T;
    for(i=0;i<T;i++)
    {
        in >> n >> k;
        out << m[n][k] << '\n';
    }
    return 0;
}