[NOI Online 2021 入门组] 切蛋糕
题目描述
Alice、Bob 和 Cindy 三个好朋友得到了一个圆形蛋糕,他们打算分享这个蛋糕。
三个人的需求量分别为 $a,b,c$,现在请你帮他们切蛋糕,规则如下:
1. 每次切蛋糕可以选择蛋糕的任意一条直径,并沿这条直径切一刀(注意切完后不会立刻将蛋糕分成两部分)。
2. 设你一共切了 $n$ 刀,那么你将得到 $2n$ 个扇形的蛋糕(特别地,切了 $0$ 刀被认为是有一个扇形,即整个圆形蛋糕),将这些蛋糕分配给 Alice,Bob 和 Cindy,要求每个扇形蛋糕只能完整地分给一个人。
3. 三人分到的蛋糕面积比需要为 $a:b:c$(不保证是最简比例,且如果 $a:b:c$ 中某个数为 $0$,表示那个人不吃蛋糕)。
为了完成这个任务,你至少需要切几刀?
输入输出格式
输入格式
本题单个测试点包含多组数据。
第一行包含一个整数 $T$,表示数据组数。
接下来 $T$ 行,每行包含三个整数 $a,b,c$,表示三人的需求量。
输出格式
输出 $T$ 行,第 $i$ 行的输出表示第 $i$ 组数据中你至少需要切蛋糕的次数。
输入输出样例
输入样例 #1
6
0 0 8
0 5 3
9 9 0
6 2 4
1 7 4
5 8 5
输出样例 #1
0
2
1
2
3
2
说明
### 样例 $1$ 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/i3pai9va.png)
### 数据范围与提示
$30\%$ 的数据满足:$a=b=0$。
$60\%$ 的数据满足:$a=0$。
$100\%$ 的数据满足:$1\le T\le 10^4,0\le a,b,c\le 10^8$,保证 $a+b+c>0$。
数据由 [SSerxhs](https://www.luogu.com.cn/user/29826) 提供。