Translated by Baidu:

Analysis:

Well, it's said that there's a O (N√N) method. But I didn't think so in the examination room. I'd like to write my O (n) algorithm.

First of all, it is obvious that if we can get together, we must satisfy a|A, b|B, c|C (divisor).

So, the problem is transformed into the number of solutions satisfying a|A, b|B and c|C in the three tuple (a, b, c) (a <= b <= c).

We use the idea of inclusion and exclusion to find out a larger set containing the solution and subtract the duplicate part.

We can first ignore the conditions (a <=b <= c), that is, without considering the order, making 1,2,3 and 1,3,2 different schemes.

Let f (x) represent the number of factors of X

The total number of such schemes is f (A) x f (B) x f (C)

Now consider what is repeated. It is not hard to think that if a, b, and c are repeatedly calculated, there must be two elements to satisfy a, b|gcd (A, B).

In this way, we can take all the statistics into account.

1, a, b|gcd (A, B), c|C

In this case, there will be two situations: (a, B, c), (B, a, c). After eliminating a=b, it will be subtracted once, so f (GCD (A, B)) minus (f (GCD (A)) 1 (2) is (f).

Similarly, there are cases of B, c|gcd (B, C), a|A, a, c|gcd (A, C), b|B.

But there is a problem, which is somewhat reduced, namely, a, B, c|gcd (A, B, C).

This is again divided into two cases:

a=b≠c:

Give a specific example to illustrate:

For example (1,2,2)

When considering GCD (A, B), we subtract once (1,2,2).

When GCD (B, C) is considered, one time (2,1,2) is subtracted

When GCD (A, C) is considered, one time (2,2,1) is subtracted

The total was subtracted 3 times. However, it was repeated 3 times at the very beginning (C13). So it was reduced.

So add it, that is, add f (GCD (A, B, C)) * (f (GCD (A, B, C))-1).

The above is divided by 2, but it is not divided by 2, because the above (a, b) and (B, a) is a situation, but here is (a, a, b) and (B, B, a), not a situation.

a≠b≠c:

Try to explain it with an example.

For example, (1,2,3) this group

When considering GCD (A, B), we subtract one (1,2,3), (1,3,2), (2,3,1).

When considering GCD (B, C), we subtract one (3,1,2), (2,1,3), (1,2,3).

When considering GCD (A, C), we subtract one (2,3,1), (3,2,1), (3,1,2).

The total was subtracted 9 times, but at the beginning it was repeated 6 times (3!). It should have been subtracted 5 times, but it has been reduced by 4 times, so it has been added 4 times.

That is to say, add f (GCD (A, B, C)) * (f (GCD (A, B, C)) -1 ) * (f (GCD (A, B, C)) — 2)/6*4

2, a, b|gcd (A, B, C), but c/|C（not divisible）, c|A, c|B

It may also be illustrated by an example.

For A=4, B=4, C=6

When the three tuple is calculated (1,2,4)

We first calculated (1,4,2), (2,4,1), (4,1,2), (4,2,1) four times.

But when we consider GCD (A, B), we subtract (1,4,2), (2,4,1).

When GCD (B, C) is considered, it is subtracted (4,1,2)

When GCD (A, C) is considered, it is subtracted (1,4,2)

So it was cut 4 times. It's going to be mended once.

So add (f (GCD (A, B))-f (GCD (A, B, C))) * f (GCD (A, B, C) *f( (GCD (A, B, C)-1)/2

In the same way, there are B, c|gcd (A, B, C), a|A but a/|gcd (A, B, C).

And a, c|gcd (A, B, C), b|B but b/|gcd (A, B, C)

3, a|gcd (A, B) but a/|C, b|gcd (B, C) but b/|A, c|gcd (A, C) but A.

For example, when A=6, B=10, C=15

Consider (2,3,5) this group

It will be calculated to (3,2,5), (2,5,3) these two times, but we did not decrease at one time.

So minus one time, that is, subtract

(f (GCD (A, B))-f (GCD (A, B, C))) * (f (GCD (B, C))-f (GCD (A, B, C))) * (f (GCD (A, C))-f (GCD (A, B, C)))

At this point, all the circumstances have been considered.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
int n;
typedef long long ll;
ll f[MAXN],num[MAXN];
int primes[MAXN],isprime[MAXN],tot;
void prepare(){
    f[1]=1;
    for(int i=2;i<=100000;i++){
        if(isprime[i]==0){
            primes[++tot]=i;
            f[i]=2;
            num[i]=1;
        }
        for(int j=1;j<=tot&&i*primes[j]<=100000;j++){
            isprime[i*primes[j]]=1;
            if(i%primes[j]==0){
                num[i*primes[j]]=num[i]+1;
                f[i*primes[j]]=f[i]/(num[i]+1ll)*(num[i*primes[j]]+1ll);
                break;
            }
            f[i*primes[j]]=f[i]*f[primes[j]];
            num[i*primes[j]]=1;
        }
    }
}
int gcd(int x,int y){
    if(y==0)
        return x;
    return gcd(y,x%y);
}
int main(){
    prepare();
    int t,a,b,c;
    SF("%d",&t);
    for(int i=1;i<=t;i++){
        SF("%d%d%d",&a,&b,&c);
        //PF("{%lld %lld %lld}\n",f[a],f[b],f[c]);
        //PF("{%d %d %d}",gcd(a,b),gcd(b,c),gcd(a,c));
        int ab=gcd(a,b),bc=gcd(b,c),ac=gcd(a,c);
        ll ans1=f[a]*f[b]*f[c]; 
        ll ans2=(f[ab]*f[ab]-f[ab])/2ll*f[c];
        ll ans3=f[a]*(f[bc]*f[bc]-f[bc])/2ll;
        ll ans4=f[b]*(f[ac]*f[ac]-f[ac])/2ll;
        int td=gcd(gcd(a,c),b);
        ll ans5=(f[td]*f[td]-f[td])+f[td]*(f[td]-1ll)*(f[td]-2ll)/6ll*4ll;
        ll ans6=(f[ab]-f[td])*f[td]*(f[td]-1ll)/2ll;
        ll ans7=(f[bc]-f[td])*f[td]*(f[td]-1ll)/2ll;
        ll ans8=(f[ac]-f[td])*f[td]*(f[td]-1ll)/2ll;
        ll ans9=(f[ab]-f[td])*(f[bc]-f[td])*(f[ac]-f[td]);
        ll ans=ans1-ans2-ans3-ans4+ans5+ans6+ans7+ans8-ans9;
        /*if(ans==212)
            PF("[%d,%d,%d]\n",a,b,c);*/
        //PF("%lld %lld %lld %lld %lld",ans1,ans2,ans3,ans4,ans5); 
        PF("%I64d\n",ans);
    }
}