#include <fstream>

using namespace std;

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

const int LIM=1000000;
int t, n, k, p[LIM+1], mat[LIM+1][8];
void ciur()
{
    p[2]=1;
    for(int i=4; i<=LIM; i+=2)
        p[i]++;
    for(int i=3; i<=LIM; i+=2)
        if(!p[i])
        {
            p[i]=1;
            for(int j=i+i; j<=LIM; j+=i)
                p[j]++;
        }
}
int main()
{
    ciur();
    for(int i=1; i<=LIM; ++i)
        for(int j=0; j<=7; ++j)
            if(p[i]==j)
                mat[i][j]=i;
            else
                mat[i][j]=mat[i-1][j];
    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        fout<<mat[n][k]<<'\n';
    }
    return 0;
}