#include <fstream>

using namespace std;

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

const int nmax= 1000000, kmax= 7;

int v[nmax+1], sol[nmax+1][kmax+1];

int main(  ) {
    for ( int i= 2; i<=nmax; i+= 2 ) {
        ++v[i];
    }
    for ( int i= 3; i<=nmax; i+= 2 ) {
        if ( v[i]==0 ) {
            for ( int j= i; j<=nmax; j+= i ) {
                ++v[j];
            }
        }
    }

    sol[1][0]= 1;
    for ( int i= 2; i<=nmax; ++i ) {
        for ( int j= 0; j<=7; ++j ) {
            sol[i][j]= sol[i-1][j];
        }
        sol[i][v[i]]= i;
    }

    int t;
    fin>>t;
    for ( int i= 0; i<t; ++i ) {
        int x, y;
        fin>>x>>y;
        fout<<sol[x][y]<<"\n";
    }
    return 0;
}