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
def prime_nums(num):
    lst = []
    for i in range(1, int(num**0.5) + 1):
        if num % i == 0:
            lst.append(i)
    st = set(lst)
    for i in lst:
        st.add(num / i)
    return st

n = int(input())
for cnt in range(n):
    [x, y, z] = input().split()
    x, y, z = int(x), int(y), int(z)
    answer = 0
    st1, st2, st3 = prime_nums(x), prime_nums(y), prime_nums(z)
    st = set()
    for i in st1:
        for j in st2:
            for k in st3:
                if i <= j <= k and x % i == 0 and y % j == 0 and z % k == 0 and ((i, j, k) in st) == False:
                    answer += 1
                    st.add((i, j, k))
                elif j <= k <= i and y % i == 0 and z % j == 0 and x % k == 0 and ((j, k, i) in st) == False:
                    answer += 1
                    st.add((j, k, i))
                elif k <= i <= j and z % i == 0 and x % j == 0 and y % k == 0 and ((k, i, j) in st) == False:
                    answer += 1
                    st.add((k, i, j))
    print(answer)
