시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB86583.333%

문제

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

Let's 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 of the input contains a single integer $t$ ($1 \le t \le 10^3$) --- the number of test cases.

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

출력

For each test case in order of input, output a single integer --- the answer to the problem.

예제 입력 1

2
7
42

예제 출력 1

3
10

힌트

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