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

题意翻译

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