J 博弈 (game)

题目描述

WIKI 和 NonFriedChips 在玩游戏，一开始序列中有 $n$ 个 $1$ ( $n$ 为偶数)，

每一轮游戏，wiki 先从序列中取出两个数字 $x,y$ ，然后删掉他们，之后NonFriedChips 要从 $x+y$ 和 $|x-y|$ 中选一个添加到序列中。

当序列中存在有某数大于其他数字之和或者所有数都是 $0$ 时结束游戏。

结束后序列中每有一个数字 NonFriedChips 就要给 WIKI 一块薯片，WIKI 希望自己拿到的薯片尽可能多， NonFriedChips 希望自己给的薯片尽可能小，两人都采用最优策略的情况下 WIKI 最多能拿到多少薯片？

输入格式

第一行一个 $t$ 表示游戏轮数

后面 $t$ 行整数 $n$ 表示每轮游戏开始时 $1$ 的个数

输出

$t$ 行整数表示两人在最优策略下 WIKI 最多拿到的薯片

输入样例

1
2

输出样例

1

数据范围

$1 \leq t \le 10^{4}$

$1 \leq n \le 10^{18}$