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 math import gcd

N = 100001
fac = [0 for i in range(N)]

for i in range(1, N):
    for j in range(i, N, i):
        fac[j] += 1

for _ in range(int(input())):
    A, B, C = map(int, input().split())
    la = fac[A]
    lb = fac[B]
    lc = fac[C]
    ab = gcd(A, B)
    ac = gcd(A, C)
    bc = gcd(B, C)
    abc = gcd(ab, C)
    dupabc = fac[abc]
    dupac = fac[ac] - dupabc
    dupbc = fac[bc] - dupabc
    dupab = fac[ab] - dupabc
    lax = la - dupabc - dupab - dupac
    lbx = lb - dupabc - dupab - dupbc
    lcx = lc - dupabc - dupac - dupbc

    ctx = lax * lbx * lc + lax * lcx * lb + lcx * lbx * la - 2 * lax * lbx * lcx

    ctx += lax * ((lb - lbx) * (lc - lcx) - (dupabc + dupbc) * (dupabc + dupbc - 1) / 2)
    ctx += lbx * ((la - lax) * (lc - lcx) - (dupabc + dupac) * (dupabc + dupac - 1) / 2)
    ctx += lcx * ((la - lax) * (lb - lbx) - (dupabc + dupab) * (dupabc + dupab - 1) / 2)

    ctx += ((dupab + dupac + dupbc + 2) * (dupab * dupac + dupab * dupbc + dupbc * dupac) - dupab * dupac * dupbc) / 2

    ctx += dupabc * (dupabc + dupab + dupac + dupbc + 2) * (dupab + dupac + dupbc) / 2

    ctx += dupabc * (dupabc + 1) * (dupabc + 2) / 6
    print(int(ctx))
