#include <chrono>
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 100005;
 
template <int N>
struct Sieve {
    int nod[N];
    constexpr Sieve() : nod() {
    //    memset(nod, 0, sizeof nod);
 for(int i = 0; i < N; i++) nod[i] = 0;
        for (int i = 1; i < N; i++)
            for(int j = i; j < N; j += i)
                nod[j]++;
    }
};
 
int fast_get_nod(int n) {
    static constexpr Sieve<MAXN> s;
    return s.nod[n];
}
 
int main()
{
    int T, a, b;
    scanf("%d", &T);
    while(T--)
    {
       scanf("%d%d", &a, &b);
       printf("%d\n", fast_get_nod[__gcd(a, b)]);
    }
}

I2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxMDAwMDU7Cgp0ZW1wbGF0ZSA8aW50IE4+CnN0cnVjdCBTaWV2ZSB7CiAgICBpbnQgbm9kW05dOwogICAgY29uc3RleHByIFNpZXZlKCkgOiBub2QoKSB7CiAgICAvLyAgICBtZW1zZXQobm9kLCAwLCBzaXplb2Ygbm9kKTsKIGZvcihpbnQgaSA9IDA7IGkgPCBOOyBpKyspIG5vZFtpXSA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBOOyBpKyspCiAgICAgICAgICAgIGZvcihpbnQgaiA9IGk7IGogPCBOOyBqICs9IGkpCiAgICAgICAgICAgICAgICBub2Rbal0rKzsKICAgIH0KfTsKCmludCBmYXN0X2dldF9ub2QoaW50IG4pIHsKICAgIHN0YXRpYyBjb25zdGV4cHIgU2lldmU8TUFYTj4gczsKICAgIHJldHVybiBzLm5vZFtuXTsKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgVCwgYSwgYjsKICAgIHNjYW5mKCIlZCIsICZUKTsKICAgIHdoaWxlKFQtLSkKICAgIHsKICAgICAgIHNjYW5mKCIlZCVkIiwgJmEsICZiKTsKICAgICAgIHByaW50ZigiJWRcbiIsIGZhc3RfZ2V0X25vZFtfX2djZChhLCBiKV0pOwogICAgfQp9

MwoxMDAwMDAgMTAwMDAwCjEyIDI0Cjc0Nzc5IDIzODMz

3
100000 100000
12 24
74779 23833