#include <bits/stdc++.h>
#define DIM 1000005

using namespace std;

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

int T,N,K;

int D[7][DIM];

int ciur[DIM];

int main(){

   for(int i=2;i<DIM;i++){
        if(!ciur[i]){
            for(int j=i+i;j<DIM;j+=i)
                ciur[j]++;
        }
        D[ciur[i]][i]=i;
    }

    for(int i=0;i<7;i++)
        for(int j=3;j<DIM;j++)
            D[i][j] = max(D[i][j],D[i][j-1]);

    fin >> T;

    while(T--){
        fin >> N >> K;
        fout << D[K][N] << "\n";
    }

}