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

using namespace std;

int t, n, k;

vector<int> ciur(NMAX), sol[8];
void creareCiur() {
    for(int i = 2; i < NMAX; i++)
        if(ciur[i] == 0)
            for(int j = i; j < NMAX; j += i)
                ciur[j]++;

    for(int i = 0; i < NMAX; i++)
    {
        if(ciur[i] > 7)
            continue;
        sol[ciur[i]].push_back(i);
    }
}

int cautBin(int st, int dr, int n, int k) {
    int mid = (st+dr)/2;
    if(st == dr) return 0;
    if(sol[k][mid] <= n && sol[k][mid+1] > n)
        return sol[k][mid];
    if(sol[k][mid] > n)
        return cautBin(st, mid, n, k);
    if(sol[k][mid] < n)
        return cautBin(mid, dr, n, k);
}

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

    creareCiur();
    scanf("%d", &t);
    for(int i = 0; i < t; ++i) {
        scanf("%d%d", &n, &k);
        printf("%d\n", cautBin(0, sol[k].size(), n, k));
    }
    return 0;
}