#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> divizori[8];
void ciur()
{
//divizori[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;
divizori[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(divizori[k][mid] <= n && divizori[k][mid+1] > n) return divizori[k][mid];
else if(divizori[k][mid] > n) return cautare(lo, mid, n, k);
else if(divizori[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;
fout << cautare(0, divizori[k].size(), n, k) << "\n";
}
return 0;
}