爱丽丝和鲍勃已经收到了三大堆糖果作为礼物。现在，他们希望将这些糖果尽可能公平地分配。为此，爱丽丝拿了一堆糖果，然后鲍勃拿了另一堆糖果。最后一堆糖果需要在爱丽丝和鲍勃之间分配(可以全给一个人)

从糖果堆中取出糖果后，如果爱丽丝的糖果比鲍勃的糖果多，她会丢弃一些糖果，以使她拥有的糖果数量等于鲍勃的糖果数量。当然，如果鲍勃有更多的糖果，他也会这样做。

爱丽丝和鲍勃都希望获得尽可能多的糖果，他们在计划划分糖果的过程。请计算此划分过程之后，爱丽丝可以拥有的最大糖果数量（当然，鲍勃将拥有相同数量的糖果）。

例如三堆糖果数量分别是1,3,4，爱丽丝可以选择数量为1的一堆，鲍勃选择数量为3的一堆，然后爱丽丝从第三堆拿3个，鲍勃拿剩下的1个，这样他们都有4个糖果了。

另一个例子是三堆糖果数量分别是1,10,100，爱丽丝可以选择数量为1的一堆，鲍勃选择数量为10的一堆，然后爱丽丝从第三堆拿54个，鲍勃拿剩下46个，此时爱丽丝55个糖果，鲍勃56个糖果，鲍勃必须扔掉一个保证两人糖果数量都是55个。

多实例，输入包含两行。

第一行一个整数t，表示有t组数据， 1<=t<=1000

第二行三个整数x,y,z，分别是三堆糖果的数量, 1<=x,y,z<=100000

输出包含t行，每行表示本组数据下两人最后拥有的糖果数量。