Alice 和 Bob 正在玩一个游戏。他们面前摆放着 $B$ 个蓝球和 $R$ 个红球。Alice 先手，之后两人轮流进行操作。Alice 随机选取一个球并将其移除。Bob 移除一个红球。

Alice 选取球时，无论球的颜色如何，她以相等的概率随机选择。Bob 移除哪一个红球并不重要。

当出现以下两种结果之一时，游戏结束： 没有蓝球了 —— Alice 获胜； 蓝球的数量严格多于红球的数量 —— Bob 获胜。

Alice 和 Bob 希望游戏结果能够平衡，他们想知道对于总球数为 $C = B + R$ 的游戏，蓝球的数量应该是多少，才能使 Alice 获胜的概率 $h$ 尽可能接近 50%。换句话说，他们想要最小化 $|h - 0.5|$ 的值。

输入的第一行包含一个整数 $G$ —— Alice 和 Bob 将要进行的比赛场数 ($1 \le G \le 10^5$)。 接下来的每一行定义了每场比赛中球的总数 $C$ ($2 \le C \le 2 \cdot 10^5$)，每场比赛占一行。

对于每场比赛，按输入顺序在单独的一行中输出使 Alice 获胜概率尽可能接近 50% 所需的蓝球数量。

样例

输入格式 1

5
2
3
6
7
8

输出格式 1

1
1
2
1
2