#include <fstream>
#include <bitset>
#define m 1000005

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

bitset<m> v;
vector <int> factori;

void ciur()
{
    v.set();
    v[1] = v[0] = 0;

    for(int i = 4 ; i <= n ; i += 2)
        v[i] = false;

    for(int i = 3 ; i * i <= n ; i += 2)
        for(int j = i * i ; j <= n ; j += i)
            v[j] = false;

}

void rez()
{
    int d = 3;

    if( !(b & 1) )
    {
        factori.push_back(2);

        while( !(b & 1) )
            b >>= 1;
    }

    while(d * d <= B)
    {
        if( !(B % d) )
        {
            factori.push_back(d);
            while( !(B % d) )
                B /= d;
        }

        d += 2;
    }

    if(B > 1)
        factori.push_back(B);

    bitset<factori.size()> comb;

    for(long long i = 1 ; i <= factori.size() *
     (factori.size() + 1) ; i++)
    {

    }
}

int main()
{
    ciur();

    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> A >> B;
        rez();
    }

    return 0;
}