要知道，计算从 111 一直到 nnn 的异或和非常容易。于是格雷码不开心，也想变得十分容易。
题目很简单，计算111到nnn的经典格雷码的异或和。
第一行给定一个T,(1≤T≤105)T,\left(1\le T \le 10^5\right)T,(1≤T≤105)，为输入样例数。
接下来TTT行分别有一个数字n,(1≤n≤1018)n,\left(1\le n \le 10^{18}\right)n,(1≤n≤1018)。
计算⊕i=1ngray(i)\oplus _{i=1}^n\text{gray}\left(i\right)⊕i=1ngray(i)，即 111 一直到 nnn 的格雷码的异或和，每行对应一个结果。
5 1 2 3 4 5
1 2 0 6 1
注册一个 猫猫星の守望 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 猫猫星の守望 通用账户
