题目描述

Alice 和 Bob 收到了三大堆糖果作为礼物。现在他们想要尽可能公平地分这些糖果。为此，Alice 先从三堆中选一堆，接着 Bob 从剩下的两堆中选一堆。最后剩下的一堆可以由 Alice 和 Bob 按照他们的意愿分配：例如，Alice 可以把这堆全拿走，Bob 一颗都不拿。

在拿完糖果后，如果 Alice 的糖果比 Bob 多，她会丢弃一些糖果，使得她和 Bob 拥有的糖果数量相等。当然，如果 Bob 的糖果更多，他也会这样做。

Alice 和 Bob 都希望自己能拿到尽可能多的糖果，并会据此安排分配过程。请你计算在这种分配方式下，Alice 最多能拿到多少颗糖果（当然，Bob 也会拿到同样多的糖果）。

你需要回答 $q$ 个独立的询问。

例如，对于 $[1, 3, 4]$，Alice 可以选择第三堆，Bob 选择第二堆，剩下的第一堆唯一的一颗糖果给 Bob——这样 Alice 有 $4$ 颗糖果，Bob 也有 $4$ 颗糖果。

再比如 $[1, 10, 100]$，Alice 可以选择第二堆，Bob 选择第一堆，第三堆的糖果可以这样分配：Bob 拿 $54$ 颗，Alice 拿 $46$ 颗。此时 Bob 有 $55$ 颗，Alice 有 $56$ 颗，Alice 需要丢弃一颗，最后两人各有 $55$ 颗。

输入格式

输入的第一行包含一个整数 $q$（$1 \le q \le 1000$），表示询问的数量。接下来有 $q$ 行，每行包含三个整数 $a, b, c$（$1 \le a, b, c \le 10^{16}$），分别表示第一、第二、第三堆糖果的数量。

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问的答案——即在双方都最优分配的情况下，Alice 最多能拿到多少颗糖果（Bob 也会拿到同样多的糖果）。

说明/提示

由 ChatGPT 4.1 翻译

样例

4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

4
55
15000000000000000
51