#10401. 切蛋糕

内存限制:256 MiB 时间限制:1000 ms 输入文件: cake.in 输出文件: cake.out
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

Alice、Bob 和 Cindy 三个好朋友得到了一个圆形蛋糕,他们打算分享这个蛋糕。

三个人的需求量分别为a , b , c ,现在请你帮他们切蛋糕,规则如下:

每次切蛋糕可以选择蛋糕的任意一条直径,并沿这条直径切一刀(注意切完后不会立刻将蛋糕分成两部分)。

设你一共切了 n 刀,那么你将得到2n 个扇形的蛋糕(特别地,切了 0 刀被认为是有一个扇形,即整个圆形蛋糕),将这些蛋糕分配给 Alice,Bob 和 Cindy,要求每个扇形蛋糕只能完整地分给一个人。

三人分到的蛋糕面积比需要为 a : b : c (不保证是最简比例,且如果 a : b : c中某个数为 0,表示那个人不吃蛋糕)。

为了完成这个任务,你至少需要切几刀?

输入格式

从文件cake.in中读入数据。

本题单个测试点包含多组数据。

第一行包含一个整数 T,表示数据组数。

接下来 T 行,每行包含三个整数 a , b , c ,表示三人的需求量。

输出格式

输出到文件cake.out中。

输出 T 行,第 i 行的输出表示第 i 组数据中你至少需要切蛋糕的次数。

样例

样例输入

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

样例解释

数据范围与提示

30%的数据满足: a=b=0。

60%的数据满足: a= 0。

100%的数据满足: 1< T≤104,0≤a,b,c≤108,保证a+b+c> 0

提示:文件输入输出请使用

freopen("cake.in", "r", stdin);
freopen("cake.out", "w", stdout);