#include <cstdio>

#define MAX_VAL 1000000
#define MAX_P 80000

bool prime[MAX_VAL];
int p[MAX_P], nrp;


void ciur() {
    for ( int i = 2; i * i < MAX_VAL; ++i )
        if ( !prime[i] )
            for ( int j = i * i; j < MAX_VAL; j += i )
                prime[j] = true;

    for ( int i = 2; i < MAX_VAL; ++i )
        if ( !prime[i] )
            p[nrp++] = i;
}

void desc( long long x, int &nr, int A[] ) {
    for ( int i = 0; i < nrp && ( long long ) p[i] * p[i] <= x; ++i )
        if ( x % p[i] == 0 ) {
            A[++nr] = p[i];

            while ( x % p[i] == 0 )
                x /= p[i];
        }
    if ( x != 1 )
        A[++nr] = x;
}

int main() {
    FILE *fin, *fout;

    ciur();

    fin = fopen( "pinex.in", "r" );
    int q;
    fscanf( fin, "%d", &q );
    while ( q ) {
        int a, b, nrpdiv, pdiv[MAX_P];
        fscanf( fin, "%lld%lld", &a, &b );

        desc( b, nrpdiv, pdiv );

        long long res = a;
        for ( int i = 1; i < ( 1 << nrpdiv ); ++i ) {
            long long nr = 0, prod = 1;

        }

        --q;
    }
}