You are given a rectangular parallelepiped with sides of positive integer lengths $A$, $B$ and $C$. 

Find the number of different groups of three integers ($a$, $b$, $c$) such that $1\leq a\leq b\leq c$ and parallelepiped $A\times B\times C$ can be paved with parallelepipeds $a\times b\times c$. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped $1\times 5\times 6$ can be divided into parallelepipeds $1\times 3\times 5$, but can not be divided into parallelepipeds $1\times 2\times 3$.
The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

Each of the next $t$ lines contains three integers $A$, $B$ and $C$ ($1 \leq A, B, C \leq 10^5$) — the sizes of the parallelepiped.
4
1 1 1
1 6 1
2 2 2
100 100 100
1
4
4
165
10
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1
1
1
1
1
1
1
1
1
1
10
9 6 8
5 5 2
8 9 2
2 7 9
6 4 10
1 1 8
2 8 1
10 6 3
7 5 2
9 5 4
41
6
21
12
39
4
7
26
8
18
1
100000 100000 100000
8436
from sys import stdin
from math import gcd


def main():
    input()
    l = stdin.read().splitlines()
    d = [3, 1, 2, 2, 2, 1] * 16667
    for i in range(4, 100001):
        for j in range(i, 100001, i):
            d[j] += 1
    for i, s in enumerate(l):
        a, b, c = map(int, s.split())
        k = gcd(b, c)
        ab = d[gcd(a, b)]
        ac = d[gcd(a, c)]
        bc = d[k]
        abc = d[gcd(a, k)]
        asz = d[a] - ab - ac + abc
        bsz = d[b] - bc - ab + abc
        csz = d[c] - ac - bc + abc
        absz = ab - abc
        bcsz = bc - abc
        acsz = ac - abc
        abcsz = abc
        l[i] = (asz * bsz * csz +
                (absz * (asz + bsz) * csz) +
                (bcsz * (bsz + csz) * asz) +
                (acsz * (asz + csz) * bsz) +
                (abcsz * (asz * bsz + asz * csz + bsz * csz)) +
                (abcsz * (absz + bcsz + acsz) * (asz + bsz + csz)) +
                ((asz + bsz + csz + absz + bcsz + acsz) * (abcsz * (abcsz + 1) // 2)) +
                (absz * bcsz * acsz) +
                ((absz * (absz + 1) * d[c]) +
                 (bcsz * (bcsz + 1) * d[a]) +
                 (acsz * (acsz + 1) * d[b])) // 2 +
                ((asz + bsz + csz + abcsz) * (absz * acsz + absz * bcsz + bcsz * acsz)) +
                (abcsz + (abcsz * (abcsz - 1)) + (abcsz * (abcsz - 1) * (abcsz - 2) // 6)))
    print('\n'.join(map(str, l)))


if __name__ == '__main__':
    main()
