该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.