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$.


-----Input-----

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.


-----Output-----

For each test case, print the number of different groups of three points that satisfy all given conditions.


-----Example-----
Input
4
1 1 1
1 6 1
2 2 2
100 100 100

Output
1
4
4
165



-----Note-----

In the first test case, rectangular parallelepiped $(1, 1, 1)$ can be only divided into rectangular parallelepiped with sizes $(1, 1, 1)$.

In the second test case, rectangular parallelepiped $(1, 6, 1)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 1, 3)$ and $(1, 1, 6)$.

In the third test case, rectangular parallelepiped $(2, 2, 2)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 2, 2)$ and $(2, 2, 2)$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'N=100001\nfac=[0 for i in range(N)]\nfor i in range(1,N):\n    for j in range(i,N,i):\n        fac[j]+=1\ndef gcd(a,b):\n        if a<b:\n            a,b=b,a\n        while b>0:\n            a,b=b,a%b\n        return a\ndef ctt(A,B,C):\n    la=fac[A]\n    lb=fac[B]\n    lc=fac[C]\n    ab=gcd(A,B)\n    ac=gcd(A,C)\n    bc=gcd(B,C)\n    abc=gcd(ab,C)\n    dupabc=fac[abc]\n    dupac=fac[ac]-dupabc\n    dupbc=fac[bc]-dupabc\n    dupab=fac[ab]-dupabc\n    lax=la-dupabc-dupab-dupac\n    lbx=lb-dupabc-dupab-dupbc\n    lcx=lc-dupabc-dupac-dupbc\n    ctx=lax*lbx*lcx\n    ctx+=lax*lbx*(lc-lcx)\n    ctx+=lax*lcx*(lb-lbx)\n    ctx+=lcx*lbx*(la-lax)\n    ctx+=lax*((lb-lbx)*(lc-lcx)-(dupabc+dupbc)*(dupabc+dupbc-1)/2)\n    ctx+=lbx*((la-lax)*(lc-lcx)-(dupabc+dupac)*(dupabc+dupac-1)/2)\n    ctx+=lcx*((la-lax)*(lb-lbx)-(dupabc+dupab)*(dupabc+dupab-1)/2)\n    ctx+=dupab*dupac*dupbc\n    ctx+=dupab*dupac*(dupab+dupac+2)/2\n    ctx+=dupab*dupbc*(dupab+dupbc+2)/2\n    ctx+=dupbc*dupac*(dupbc+dupac+2)/2\n    ctx+=dupabc*(dupab*dupac+dupab*dupbc+dupbc*dupac)\n    ctx+=dupabc*(dupab*(dupab+1)+(dupbc+1)*dupbc+(dupac+1)*dupac)/2\n    ctx+=(dupabc+1)*dupabc*(dupab+dupac+dupbc)/2\n    ctx+=(dupabc*dupabc+dupabc*(dupabc-1)*(dupabc-2)/6)\n    return int(ctx)\nn=int(input())\nfor _ in range(n):\n    a,b,c = map(int,input().split())\n    print(ctt(a,b,c))\nreturn'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: