Pave the Parallelepiped

题意翻译

给你一个长方体,三边长分别为 $A,B,C$($A,B,C\leqslant100000$)。 请你求出有多少个三元组 $(a,b,c)$ 满足: - $1\leqslant a\leqslant b\leqslant c$; - 原长方体可以由若干个三边长为 $a,b,c$ 的长方体密铺成。 注意:你可以调整小长方体的长宽高顺序,但必须保证所有小长方体朝向一致。 例如,长方体 $1\times5\times6$ 可以由长方体 $1\times3\times5$ 密铺得到,但不能由长方体 $1\times2\times3$ 密铺得到。

题目描述

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