#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 1e6 + 5;

vector<int>g[8];
int c[N_MAX];

void precalc(){
    c[0] = c[1] = 0;
    for (int i=2; i*i<N_MAX; i++){
        if (c[i] == 0){
            c[i] = 1;
            for (int j=2*i; j<N_MAX; j+=i){
                c[j] += 1;
            }
        }
    }
    for (int i=1; i<N_MAX; i++){
        if (c[i] <= 7){
            g[c[i]].push_back(i);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    precalc();
    int t; fin >> t;
    while (t--){
        int x , k; fin >> x >> k;
        int st = 0 , dr = g[k].size() - 1, ans = g[k].size() - 1;
        while (st <= dr){
            int mij = (st + dr) / 2;
            if (g[k][mij] > x){
                ans = min(mij , ans) , dr = mij - 1;
            }
            else{
                st = mij + 1;
            }
        }
        fout << ((ans == 0) ? 0 : g[k][ans - 1]) << '\n';
    }
}