#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int a[8000005],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[8000005];
int cb(int p, int k)
{
    int mijl,st,dr;
    st = 1, dr = p;
    while(st <= dr)
    {
        mijl = (st+dr)/2;
        if(x[k][mijl] > p)
            dr = mijl - 1;
        else st = mijl + 1;
    }
    if(x[k][mijl - 1] > n) return 0;
    return x[k][mijl - 1];
}
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++)
        x[a[i]].push_back(i);
    for(i = 1; i <= p; i++)
    {
        fin >> n >> k;
        fout << cb(n,k) << "\n";
    }
    return 0;
}