Pave the Parallelepiped

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a rectangular parallelepiped with sides of positive integer lengths $\mathrm{AA, BB and CC.}$

Find the number of different groups of three integers ($\mathrm{aa, bb, cc)\; such\; that 1\le a\le b\le c1\le a\le b\le c and\; parallelepiped A\times B\times CA\times B\times C can\; be\; paved\; with\; parallelepipeds a\times b\times ca\times b\times c.\; Note,\; that\; all\; small\; parallelepipeds have\; to\; be\; rotated\; in\; the\; same\; direction.}$

For example, parallelepiped $\mathrm{1\times 5\times 61\times 5\times 6 can\; be\; divided\; into\; parallelepipeds 1\times 3\times 51\times 3\times 5,\; but\; can\; not\; be\; divided\; into\; parallelepipeds 1\times 2\times 31\times 2\times 3.}$

Input

The first line contains a single integer $\mathrm{tt (1\le t\le 1051\le t\le 105) —\; the\; number\; of\; test\; cases.}$

Each of the next $\mathrm{tt lines\; contains\; three\; integers AA, BB and CC (1\le A,B,C\le 1051\le A,B,C\le 105) —\; 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

Copy

4 1 1 1 1 6 1 2 2 2 100 100 100

output

Copy

1 4 4 165

Note

In the first test case, rectangular parallelepiped $(1,1,1)(1,1,1) can\; be\; only\; divided\; into\; rectangular\; parallelepiped\; with\; sizes (1,1,1)(1,1,1).$

In the second test case, rectangular parallelepiped $(1,6,1)(1,6,1) can\; be\; divided\; into\; rectangular\; parallelepipeds\; with\; sizes (1,1,1)(1,1,1), (1,1,2)(1,1,2), (1,1,3)(1,1,3) and (1,1,6)(1,1,6).$

In the third test case, rectangular parallelepiped $(2,2,2)(2,2,2) can\; be\; divided\; into\; rectangular\; parallelepipeds\; with\; sizes (1,1,1)(1,1,1), (1,1,2)(1,1,2), (1,2,2)(1,2,2) and (2,2,2)(2,2,2).$

 

情况分为四种：a，b重负的情况；a，c重复的情况；b，c重复的情况；a，b，c重复的情况

#include