Problem Description

Alice, Bob, and Cindy, three good friends, got a circular cake and plan to share it.

Their required amounts are $a, b, c$, respectively. Now please help them cut the cake under the following rules:

1. Each time you cut the cake, you may choose any diameter of the cake and make one cut along this diameter (note that after cutting, the cake will not be immediately separated into two parts).

2. Suppose you make a total of $n$ cuts. Then you will obtain $2n$ sector-shaped pieces of cake (in particular, making $0$ cuts is considered to give one sector, i.e., the whole circular cake). Distribute these pieces to Alice, Bob, and Cindy, and each sector-shaped piece must be given entirely to exactly one person.

3. The ratio of the cake areas received by the three people must be $a:b:c$ (it is not guaranteed to be in simplest form, and if some number in $a:b:c$ is $0$, it means that person does not eat cake).

To complete this task, what is the minimum number of cuts you need to make?

Input Format

This problem contains multiple test cases in a single test point.

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain three integers $a, b, c$, representing the required amounts of the three people.

Output Format

Output $T$ lines. The output on the $i$-th line indicates the minimum number of cuts needed for the $i$-th test case.

6
0 0 8
0 5 3
9 9 0
6 2 4
1 7 4
5 8 5

0
2
1
2
3
2

Hint

Explanation for Sample $1$

Constraints and Notes

$30\%$ of the testdata satisfies: $a=b=0$.

$60\%$ of the testdata satisfies: $a=0$.

$100\%$ of the testdata satisfies: $1\le T\le 10^4，0\le a,b,c\le 10^8$，and it is guaranteed that $a+b+c>0$.

The testdata is provided by SSerxhs.

Translated by ChatGPT 5