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
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
def gcd(a,b):
        if a<b:
            a,b=b,a
        while b>0:
            a,b=b,a%b
        return a
def ctt(A,B,C):
    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*lcx
    ctx+=lax*lbx*(lc-lcx)
    ctx+=lax*lcx*(lb-lbx)
    ctx+=lcx*lbx*(la-lax)
    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
    ctx+=dupab*dupac*(dupab+dupac+2)/2
    ctx+=dupab*dupbc*(dupab+dupbc+2)/2
    ctx+=dupbc*dupac*(dupbc+dupac+2)/2
    ctx+=dupabc*(dupab*dupac+dupab*dupbc+dupbc*dupac)
    ctx+=dupabc*(dupab*(dupab+1)+(dupbc+1)*dupbc+(dupac+1)*dupac)/2
    ctx+=(dupabc+1)*dupabc*(dupab+dupac+dupbc)/2
    ctx+=(dupabc*dupabc+dupabc*(dupabc-1)*(dupabc-2)/6)
    return ctx
n=int(input())
for _ in range(n):
    a,b,c = map(int, input().split())
    print(ctt(a,b,c))
exit()