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

using namespace std;

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

int T,N,K;

int D[8][DIM];

int ciur[DIM];

int main(){

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

    for(int i=1;i<8;i++)
        for(int j=2;j<DIM;j++)
            if(ciur[j]==i){
                D[i][j]=j;
            }
            else
                D[i][j]=D[i][j-1];

    fin >> T;

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

}