Believer

Do you believe in dragons? Imagine one of them wakes you up at night and asks the following.

Consider sequences of positive integers $a = \langle a_1, a_2, \ldots, a_k \rangle$.

Let $f(a, x)$ be the number of occurrences of $x$ in $a$. For example, $f(\langle 1, 4, 1, 1 \rangle, 1) = 3$.

Let $c(y)$ be the number of ones in the binary expansion of $y$. For example, $c(13) = c(1101_2) = 3$.

Let $b(a) = \sum \limits_{i \in a} c(f(a, i))$. For example, $b(\langle 1, 4, 1, 1 \rangle) = c(3) + c(1) = 2 + 1 = 3$.

For the given value of $n$, find the maximum value of $b(a)$ over all sequences with $\sum \limits_{i=1}^{k} a_i = n$.

What would you answer?

The first line contains a single integer $t$ ($1 \le t \le 10^3$).

Each of the next $t$ lines contains a single integer $n$ ($1 \le n \le 10^{18}$).

For each test case, in the order of the input, print a single integer on its own line: the answer to the problem.

In the first example, one sequence with $b(a) = 3$ is $a = \langle 1, 4, 1, 1 \rangle$.