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
t = int(input())
tc = 1
from math import sqrt
while tc <= t:
    tc += 1
    a, b, c = input().split(' ')
    a, b, c = int(a), int(b), int(c)
    if a > b:
        a, b = b, a
    if b > c:
        b, c = c, b
    Da = []
    for j in range(1, int(sqrt(a))+1):
        if a % j == 0:
            Da.append(j)
    for j in range(len(Da)-1, -1, -1):
        if a // Da[j] > Da[j]:
            Da.append(a // Da[j])
    Db = []
    for j in range(1, int(sqrt(b))+1):
        if b % j == 0:
            Db.append(j)
    for j in range(len(Db)-1, -1, -1):
        if b // Db[j] > Db[j]:
            Db.append(b // Db[j])
    Dc = []
    for j in range(1, int(sqrt(c))+1):
        if c % j == 0:
            Dc.append(j)
    for j in range(len(Dc)-1, -1, -1):
        if c // Dc[j] > Dc[j]:
            Dc.append(c // Dc[j])
    L = []
    f = 0
    g = 0
    while f < len(Db):
        while g < len(Dc) and Dc[g] < Db[f]:
            g+=1
        L.append(len(Dc)-g)
        f+=1
    h = len(L)-2
    while h >= 0:
        L[h] += L[h+1]
        h-=1
    L.append(0)
    sol = 0
    f = 0
    g = 0
    while f < len(Da):
        while g < len(Db) and Db[g] < Da[f]:
            g+=1
        sol += L[g]
        f+=1
    print(sol)
