시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 8 | 6 | 5 | 83.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.
2 7 42
3 10
In the first example test case, one possible sequence with $b(a) = 3$ is $a = \langle 1, 4, 1, 1 \rangle$.