Description

Given a square, find how many points inside the square satisfy that the ratio of the areas of the four parts divided by the four vertices of the square is $a:b:c:d$. The four numbers are unordered.

For example, as shown in the figure below, suppose there is a point $E$ such that the area ratio of the four triangles is $a:b:c:d$, then point $E$ meets the requirement. Since the order does not matter, a ratio like $d:b:a:c$ is also acceptable. However, point $E$ is not the only solution; you need to output the number of solutions.

Since little S, little Q, little U, little A, little R, and little E like asking questions very much, this problem provides $q$ queries.

Input Format

The first line contains an integer $q$, representing the number of queries.
The next $q$ lines each contain four integers $a,b,c,d$.

Output Format

Output $q$ lines, each line containing an integer representing the answer.

3
1 3 3 1
2 4 7 8
2 3 1 4

4
0
8

Hint

Constraints

For $20\%$ of the testdata, $a=b=c=d$.
For $100\%$ of the testdata, $1 \le a,b,c,d \le 9 \times 10^{18}$, $1 \le q \le 100$. It is not guaranteed that $a:b:c:d$ is in simplest form, and it is not guaranteed that $a,b,c,d$ are in increasing order.

Translated by ChatGPT 5