#include <fstream>

using namespace std;

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

const int nmax = 1e6, kmax = 7;
int nrq, n, k;

int primediv[nmax + 2];
int answer[kmax + 2][nmax + 2];

int main(){

    for(int i = 2; i <= nmax; i++){
        if(!primediv[i]){
            for(int j = i; j <= nmax; j += i)
                primediv[j]++;
        }
    }

    for(int k = 1; k <= kmax; k++){
        for(int i = 1; i <= nmax; i++){
            answer[k][i] = answer[k][i - 1];
            if(primediv[i] == k)
                answer[k][i] = i;
        }
    }

    in>>nrq;
    for(int __q = 1; __q <= nrq; __q++){
        in>>n>>k;
        if(k == 0){
            out<<"1\n"; continue;
        }else{ out<<answer[k][n]<<"\n"; }
    }

    return 0;
}