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
import sys
import math
from functools import reduce

def factors(n):
    seta=set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    return sorted(list(seta))

n=int(input())
for _ in range(n):
    lisa = []
    a,b,c=map(int,input().strip().split())
    fa,fb,fc=factors(a),factors(b),factors(c)
    #print(fa,fb,fc)
    x,y,z=0,0,0
    for i in range(len(fa)):
        stra=[]
        x=str(fa[i])
        stra.append(x)
        for j in range(len(fb)):
            #print("Printing y values y=",fb[j])
            y=str(fb[j])
            stra.append(y)
            for k in range(len(fc)):
                z=str(fc[k])
                stra.append(z)
                cv=''.join(sorted(stra))
                lisa.append(cv)
                stra.pop()
            stra.pop()
        stra.pop()
    meta=set(lisa)
    #print(lisa)
    #print(meta)
    print(len(meta))