#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int SIZE = 1000002;

int t, n, k;

int d[SIZE];
vector<int> nr[8];

void read();
void solve();

int main()
{
    read();
    solve();
    return 0;
}

void read()
{
    fin >> t;
}


void solve()
{
    for(int i = 2; i < SIZE; ++i)
        if(d[i] == 0)
            for(int j = i; j < SIZE; j += i)
                d[j] += 1;

    for(int i = 2; i <= 1e6; ++i)
        if(d[i] < 8)
            nr[d[i]].push_back(i);

    for(int i = 1; i <= t; ++i)
    {
        cin >> n >> k;

        int res = lower_bound(nr[k].begin(), nr[k].end(), n) - nr[k].begin() - 1;

        fout << (res < 0 ? 0 : nr[k][res]) << "\n";
    }
}