Pave the Parallelepiped
题意翻译
$t$ 组询问,每组输入 $A,B,C$,输出满足以下条件的有序数组 $(a,b,c)$ 的个数。
- $1 \le a \le b \le c$
- 存在一个 $a, b, c$ 的排列 $a', b', c'$,使 $a'|A, b'|B, c'|C$。
$t, A, B, C \le 10^5$
题目描述
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.
输出格式
For each test case, print the number of different groups of three points that satisfy all given conditions.
输入输出样例
输入样例 #1
4
1 1 1
1 6 1
2 2 2
100 100 100
输出样例 #1
1
4
4
165
说明
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) $ .