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

Difficulty: VERY_HARD
Tags: Bit manipulation

Combinatorics

Complete search

Number theory

Mathematics
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
from sys import stdin
from math import gcd

def main():
	input()
	l = stdin.read().splitlines()
	d = [3.0, 1.0, 2.0, 2.0, 2.0, 1.0] * 16667
	for i in range(4, 100001):
		for j in range(i, 100001, i):
			d[j] += 1.0
	for (i, s) in enumerate(l):
		(a, b, c) = map(int, s.split())
		k = gcd(b, c)
		ab = d[gcd(a, b)]
		ac = d[gcd(a, c)]
		bc = d[k]
		abc = d[gcd(a, k)]
		asz = d[a] - ab - ac + abc
		bsz = d[b] - bc - ab + abc
		csz = d[c] - ac - bc + abc
		absz = ab - abc
		bcsz = bc - abc
		acsz = ac - abc
		l[i] = '%d' % (asz * bsz * csz + absz * (asz + bsz) * csz + bcsz * (bsz + csz) * asz + acsz * (asz + csz) * bsz + abc * (asz * bsz + asz * csz + bsz * csz) + abc * (absz + bcsz + acsz) * (asz + bsz + csz) + (asz + bsz + csz + absz + bcsz + acsz) * (abc * (abc + 1) * 0.5) + absz * bcsz * acsz + (absz * (absz + 1.0) * d[c] + bcsz * (bcsz + 1.0) * d[a] + acsz * (acsz + 1.0) * d[b]) * 0.5 + (asz + bsz + csz + abc) * (absz * acsz + absz * bcsz + bcsz * acsz) + (abc + abc * (abc - 1.0) + abc * (abc - 1.0) * (abc - 2.0) / 6.0))
	print('\n'.join(map(str, l)))
main()


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 int(ctx)
n = int(input())
for _ in range(n):
	(a, b, c) = map(int, input().split())
	print(ctt(a, b, c))
return