Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Pave the Parallelepiped

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 11:32:30 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|