你的朋友刚学了位运算，但并不是特别的精通，他知道你是位运算大师，于是拿着下面这段伪代码来问你：
```cpp
Input N
T = 0
While True:
X = N # (N - 1)
If N == X:
Break
End If
T = T + 1
N = X
End While
Output T
```
他定义了三个函数 $f(x),g(x),h(x)$，分别表示当上述伪代码中的 `#` 符号被替换为 `&`（按位与）、`|`（按位或）以及 `^`（按位异或）这三种运算符之后，输入 $x$ 所得到的结果。
他给了你一个 $n$，请你帮助他求出这三个函数的前缀和 $\sum\limits_{x=1}^nf(x), \sum\limits_{x=1}^ng(x), \sum\limits_{x=1}^nh(x)$.
输入格式
第一行包含一个整数 $T$ $(1 \le T \le 10^5)$，表示测试数据组数。
每组数据占一行，包含一个整数 $n$ $(1 \le n \le 2^{56})$.