#include <fstream>
#include <vector>

using namespace std;

#define Nmax 1000000

vector<int> v[8];
vector<int>::iterator it;

int ciur[Nmax];

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

    int t, i, j, n, x;

    fin >> t;

    ciur[0] = 1;
    ciur[1] = 1;

    for(i = 2; i * i <= Nmax; i++)
    {
        if(ciur[i] == 0)
        {
            for(j = i * i; j <= Nmax; j += i)
            {
                ciur[j]++;
            }
        }
    }

    for(i = 2; i <= Nmax; i++)
    {
        v[ciur[i]].push_back(i);
    }

    for(i = 1; i <= n; i++)
    {
        fin >> n >> x;
        /*it = v[x].lower_bound(n);
        if(it == v[x].end())
        {
            fout << 0;
        }
        else
        {
            fout << *it;
        }
        fout << '\n';*/
    }
    return 0;
}