C. 【GENOIP#45】dawn
题目描述
黎明卿要去深渊探险。
为了保证能从“来无回之都”返回，黎明卿决定制作一些弹药包。
现在有 $n$ 个人，第 $i$ 个人编号为 $i$ ，他们排成一个环。
为了让制作弹药包的过程有趣一些，黎明卿决定将编号为 $1$ 的人做成弹药包，然后在环上每隔一个当前还没被做成弹药包的人并将下一个当前还没被做成弹药包的人做成弹药包。特别的，当本次选择时只剩下最后一个人时，黎明卿也会把他做成弹药包（而不会像传统约瑟夫游戏一样留下 $1$ 个人）。
将编号为 $i$ 的人做成弹药包会获得一堆共有 $i$ 颗“生命回响之石”的石子堆。
现在黎明卿想知道，存在多少种局面，使得在现存的石子堆玩 Nim 游戏（不能取的人为败），先手有必胜策略。
局面定义：初始 $n$ 个人都没有被做成弹药包为局面 $0$ ，接下来进行操作，第 $i$ 次操作后的局面定义为局面 $i$ ，由于一共有 $n$ 个人，故总局面数量为 $n+1$ ，标号为局面 $0$ 到局面 $n$ 。
Nim 游戏：有若干堆石子，每堆石子的数量都是有限的。两人轮流行动，合法的行动是“选择一堆石子并拿走若干颗（不能不拿）”，拿走最后一颗石子的人获胜。
输入格式
数据包含多组询问，首先输入数据第一行包含一个整数 $T$ 。
接下来 $T$ 行每行一个整数 $n$ ，表示一个询问的 $n$ 。
输出格式
输出 $T$ 行每行一个整数，表示 $n$ 个人的游戏中有多少个局面使得在现存的石子堆上玩 Nim 游戏使得先手必胜。
样例 1
数据范围与提示
样例解释
当 $n=5$ 时，
局面 $0$ ：当前人为 $1,2,3,4,5$ ，没有石子堆，先手必败；
局面 $1$ ：当前人为 $2,3,4,5$ ，石子堆为 $1$ ，先手必胜；
局面 $2$ ：当前人为 $2,4,5$ ，石子堆为 $1,3$ ，先手必胜；
局面 $3$ ：当前人为 $2,4$ ，石子堆为 $1,3,5$ ，先手必胜；
局面 $4$ ：当前人为 $2$ ，石子堆为 $1,3,5,4$ ，先手必胜；
局面 $5$ ：当前没有人，石子堆 $1,3,5,4,2$ ，先手必胜。
数据范围
对于前 $20\%$ 的数据， $1\le T\le 10^3$ ， $0 \le n\leq 10^4$ ；
对于 $100\%$ 的数据， $1\leq T\leq 10^4$ ， $0\leq n<10^{18}$ 。