#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int a[1000005],n,p,k;
/**

*/
/**
0 1 2 3 4 5 6 7 8 9 10
0 1 1 1 1 1 2 1 1 1 2

0 1 2 3 4 5 7 8 9 6 10
0 1 1 1 1 1 1 1 1 2  2
*/
vector<int> x[10];
int cb(int p, int k)
{
    int mijl,st,dr,t = 0;
    st = 0, dr = x[k].size() - 1;
    if(x[k][0] > p) return 0;
    if(x[k][dr] < p) return x[k][dr];
    while(st <= dr)
    {
        mijl = (st+dr)/2;
        if(x[k][mijl] > p)
            dr = mijl - 1;
        else
        {
            t = mijl;
            st = mijl + 1;
        }
    }
    return x[k][t];
}
int main()
{
    int i,j;
    fin >> p;
    for(i = 2; i <= 1000000; i++)
        if(a[i] == 0)
            for(j = i; j <= 1000000; j += i)
                a[j]++;
    for(i = 1; i <= 1000000; i++)
        if(a[i] <= 7)
            x[a[i]].push_back(i);
    for(i = 1; i <= p; i++)
    {
        fin >> n >> k;
        fout << cb(n,k) << "\n";
    }
    return 0;
}