#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 1000000;
int v[NMAX + 5],M[NMAX + 5][8],Query,n,m;

void Sieve(){
    for(int i = 2;i <= NMAX;i++){
        if(v[i] == 0)
            for(int j = i;j <= NMAX;j += i)
                v[j]++;
        M[i][v[i]] = i;
    }
    for(int j = 0;j <= 7;j++)
        for(int i = 0;i <= NMAX;i++)
            if(M[i][j] == 0)
                M[i][j] = M[i - 1][j];
}

int main(){
    Sieve();
    f >> Query;
    while(Query--){
        f >> n >> m;
        g << M[n][m] << "\n";
    }
}