#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX = 1000005;

int a[MAX];
vector<int> div[8];

void ciur()
{
    //div[0][0] = 0;
    for(int i = 2; i < MAX; i++)
        if(a[i] == 0)
            for(int j = i; j < MAX; j += i)
                a[j]++;
    for(int i = 0; i < MAX; i++)
    {
        if(a[i] > 7)
            continue;
        div[a[i]].push_back(i);
    }
}

int cautare(int lo, int hi, int n, int k)
{
    int mid = (lo+hi)/2;
    if(lo == hi) return 0;
    if(div[k][mid] <= n && div[k][mid+1] > n) return div[k][mid];
    else if(div[k][mid] > n) return cautare(lo, mid, n, k);
    else if(div[k][mid] < n) return cautare(mid, hi, n, k);
}

int main()
{
    int T, n, k;
    fin >> T;
    ciur();
    for(int in = 0; in < T; in++)
    {
        fin >> n >> k;

        cout << cautare(0, div[k].size(), n, k) << "\n";
    }
    return 0;
}