#include <bits/stdc++.h>
using namespace std;
#define MAX 10000000
vector <int> primes;
int prime[MAX];
int setBit( int n, int position ) {
    n = n | ( 1 << position );
    return n;
}
bool checkBit(int n, int position) {
    return n & ( 1 << position );
}
void primeGenerator( int n ) {
    int x = sqrt( n );
    primes.push_back(2);
    prime[0] = setBit( prime[0], 0 );
    prime[0] = setBit( prime[0], 1 );
    for( int i = 4; i <= n; i += 2 )
       prime[ i >> 5 ] = setBit( prime[ i >> 5 ], i & 31 );
    for( int i = 3; i <= x; i += 2 ) {
       if( !checkBit( prime[ i >> 5 ], i & 31 ) ) {
            primes.push_back(i);
            for( int j = i+i; j <= n; j += i )
                prime[ j >> 5 ] = setBit( prime[ j >> 5 ], j & 31 );
        }
    }
    return;
}
int main() {
    primeGenerator(10000000);
    int T;

    scanf("%d", &T);
    int cs;

    for (cs=1; cs<=T; cs++) {
        vector <int> ber;
        vector <int> aer;
        long long int a, b;
        scanf("%lld %lld", &a, &b);
        long long int i;
        for (i=0; primes[i]*primes[i] <= b; i++) {
            if (b % primes[i] == 0) {
                while (b%primes[i] == 0) {
                    ber.push_back(primes[i]);
                    b/=primes[i];
                }
            }
        }
        if (b>=2) ber.push_back(b);
        for (i=0; primes[i]*primes[i] <= a; i++) {
            if (a % primes[i] == 0) {
                while (a%primes[i] == 0) {
                    aer.push_back(primes[i]);
                    a/=primes[i];
                }
            }
        }
        if (a>=2) aer.push_back(a);

    }
    return 0;
}