Background

Special for beginners, ^_^

Description

输入三个正整数X、Y和Z，求方程x+y+z = lcm(x, y, z)的整数解数量。 其中1<=x<=X, 1<=y<=Y，1<=z<=Z; 三个数的和等于三个数的最小公倍数。

Format

Input

T组数据，输入的第一行包括一个正整数T; 接下来T行每组包含三个正整数X,Y,Z(不超过1e11)。

Output

共T行，对于每组数据，输出满足条件的三元组(x,y,z)的个数。

Samples

2
1 1 1
2 2 2

0
0

Limitation

1s, 1024KiB for each test case.