{"raw_statement":[{"iden":"statement","content":"You are given a rectangular parallelepiped with sides of positive integer lengths $A$, $B$ and $C$.\n\nFind 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**.\n\nFor 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$."},{"iden":"input","content":"The first line contains a single integer $t$ ($1 \\leq t \\leq 10^5$) — the number of test cases.\n\nEach 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."},{"iden":"output","content":"For each test case, print the number of different groups of three points that satisfy all given conditions."},{"iden":"example","content":"Input\n\n4\n1 1 1\n1 6 1\n2 2 2\n100 100 100\n\nOutput\n\n1\n4\n4\n165"},{"iden":"note","content":"In the first test case, rectangular parallelepiped $(1, 1, 1)$ can be only divided into rectangular parallelepiped with sizes $(1, 1, 1)$.\n\nIn 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)$.\n\nIn 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)$."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"给你一个边长为正整数 $A$、$B$ 和 $C$ 的长方体。\\n\\n求满足 $1 lt.eq a lt.eq b lt.eq c$ 的不同三元组 $(a, b, c)$ 的数量，使得尺寸为 $A \\\\times B \\\\times C$ 的长方体可以被若干个尺寸为 $a \\\\times b \\\\times c$ 的小长方体完全铺满。注意，所有小长方体必须以相同的方向旋转。\\n\\n例如，尺寸为 $1 \\\\times 5 \\\\times 6$ 的长方体可以被划分为尺寸为 $1 \\\\times 3 \\\\times 5$ 的长方体，但不能被划分为尺寸为 $1 \\\\times 2 \\\\times 3$ 的长方体。\\n\\n第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^5$) —— 测试用例的数量。\\n\\n接下来的 $t$ 行每行包含三个整数 $A$、$B$ 和 $C$ ($1 lt.eq A, B, C lt.eq 10^5$) —— 长方体的尺寸。\\n\\n对于每个测试用例，输出满足所有给定条件的不同三元组的数量。\\n\\n在第一个测试用例中，长方体 $(1, 1, 1)$ 只能被划分为尺寸为 $(1, 1, 1)$ 的长方体。\\n\\n在第二个测试用例中，长方体 $(1, 6, 1)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 1, 3)$ 和 $(1, 1, 6)$ 的长方体。\\n\\n在第三个测试用例中，长方体 $(2, 2, 2)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 2, 2)$ 和 $(2, 2, 2)$ 的长方体。 \"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^5$) —— 测试用例的数量。接下来的 $t$ 行每行包含三个整数 $A$、$B$ 和 $C$ ($1 lt.eq A, B, C lt.eq 10^5$) —— 长方体的尺寸。\"},{\"iden\":\"output\",\"content\":\"对于每个测试用例，输出满足所有给定条件的不同三元组的数量。\"},{\"iden\":\"note\",\"content\":\"在第一个测试用例中，长方体 $(1, 1, 1)$ 只能被划分为尺寸为 $(1, 1, 1)$ 的长方体。在第二个测试用例中，长方体 $(1, 6, 1)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 1, 3)$ 和 $(1, 1, 6)$ 的长方体。在第三个测试用例中，长方体 $(2, 2, 2)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 2, 2)$ 和 $(2, 2, 2)$ 的长方体。 \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ T = \\{(A_k, B_k, C_k) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of test cases, where for each $ k $:  \n- $ A_k, B_k, C_k \\in \\mathbb{Z}^+ $ denote the side lengths of the large rectangular parallelepiped.  \n\nLet $ \\mathcal{P} $ be the set of all ordered triples $ (a, b, c) \\in \\mathbb{Z}^3 $ such that $ 1 \\le a \\le b \\le c $.  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. For each $ k \\in \\{1, \\dots, t\\} $:  \n   - $ 1 \\le A_k, B_k, C_k \\le 10^5 $  \n\n**Objective**  \nFor each test case $ (A, B, C) $, compute the number of triples $ (a, b, c) \\in \\mathcal{P} $ such that:  \n$$\na \\mid A,\\quad b \\mid B,\\quad c \\mid C \\quad \\text{or any permutation of } (a,b,c) \\text{ divides } (A,B,C) \\text{ in some order}.\n$$\n\n**Clarification (from problem context)**  \nThe small parallelepiped $ a \\times b \\times c $ must tile the large one $ A \\times B \\times C $ with all small parallelepipeds oriented identically (i.e., no rotation among small blocks; the entire tiling uses the same alignment). This implies that $ (a,b,c) $ must be a *direct divisor triple*: there exists a permutation $ \\sigma \\in S_3 $ such that:  \n$$\na \\mid A_{\\sigma(1)}, \\quad b \\mid A_{\\sigma(2)}, \\quad c \\mid A_{\\sigma(3)},\n$$  \nwhere $ (A_{\\sigma(1)}, A_{\\sigma(2)}, A_{\\sigma(3)}) $ is a sorted version of $ (A,B,C) $. But since $ a \\le b \\le c $, and tiling requires alignment, the only valid configuration is when $ (a,b,c) $ divides $ (A,B,C) $ **after sorting both triples in non-decreasing order**.\n\nThus, define:  \nLet $ (A', B', C') $ be the sorted version of $ (A, B, C) $, i.e., $ A' \\le B' \\le C' $.  \nThen $ (a, b, c) \\in \\mathcal{P} $ is valid if and only if:  \n$$\na \\mid A', \\quad b \\mid B', \\quad c \\mid C'.\n$$\n\n**Final Objective**  \nFor each test case $ (A, B, C) $, let $ (A', B', C') = \\text{sort}(A, B, C) $.  \nCompute:  \n$$\n\\left| \\left\\{ (a, b, c) \\in \\mathbb{Z}^3 \\,\\middle|\\, 1 \\le a \\le b \\le c,\\ a \\mid A',\\ b \\mid B',\\ c \\mid C' \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}