#include <bits/stdc++.h>

using namespace std;

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

const int dim = 1e6+1;
unsigned short d[dim];

vector<int>v[8];

int main()
{
    for (int i=2; i<dim; i++)
    {
        if (!d[i])
        {
            for (int j=i; j<dim; j+=i)
                d[j]++;
        }
    }

    for (int i=1; i<dim; i++)
        v[d[i]].push_back(i);

    int t;
    in >> t;

    while (t--)
    {
        int n, k;
        in >> n >> k;

        int l=0, r = int(v[k].size())-1;
        int sol = -1;

        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (v[k][mid] <= n)
                sol = mid, l = mid + 1;
            else
                r = mid - 1;
        }

        if (sol == -1)
            out << 0;
        else
            out << v[k][sol];
        out << '\n';
    }

    return 0;
}