#include<iostream>
#include<fstream>

using namespace std;

int a[9][1000000], u[9];
int e[1000005];

int bsearch(int n, int k){
    int p = 0, ul = u[k]-1, sol = 0, m;
    
    while (p <= ul){
        m = (p+ul)/2;
        if (a[k][m] <= n){
             sol = a[k][m];
             p = m+1;
        }
        else 
            ul = m-1;
    }
    return sol;   
}

int main(){
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int n, k;
    int i, j;
    
    for (i = 2; i <= 1000000; i++)
        if (e[i] == 0)
            for (j = i; j <= 1000000; j = j+i)
                e[j] = e[j] + 1;  
    
    for (i = 1; i <= 1000000; i++){
        a[e[i]][u[e[i]]] = i;  
        u[e[i]]++;
    }
    
    int t;
    f>>t;
    for (i = 1; i <= t; i++){
        f>>n>>k;
        g<<bsearch(n, k)<<'\n';    
    }
    return 0;
}