#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;

bool c[5 + N] = {1, 1};
char dv[5 + N];
vector <int> primes;

int a[10][5 + N];

void ciur() {
    for(int i = 2; i * i <= N; i++) {
        if(c[i] == false)
            for(int j = i * i; j <= N; j += i)
                c[j] = true;
    }
    for(int i = 2; i <= N; i++)
        if(c[i] == false)
            primes.push_back(i);
}

void find_divizori() {
    dv[1] = 0;

    for(auto it : primes){
        for(int j = 1; j * it <= N; j++)
            dv[j * it]++;
    }

    for(int i = 2; i <= N; i++){
        int nrdiv = dv[i];
        a[nrdiv][++a[nrdiv][0]] = i;
    }
}

int solve(int n, int k){
    int st, dr, mid, ans(0);
    st = 1;
    dr = a[k][0];

    while(st <= dr){
        mid = (st + dr) >> 1;
        if(a[k][mid] <= n){
            ans = a[k][mid];
            st = mid + 1;
        } else dr = mid - 1;
    }

    return ans;
}

int main() {
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);

    ciur();
    find_divizori();

    int t, n, k;
    scanf("%d", &t);

    while(t--){
        scanf("%d%d", &n, &k);
        printf("%d\n", solve(n, k));
    }
    return 0;
}