Believer

용을 믿는가? 밤에 용이 깨어나서 이런 질문을 던진다고 상상해 보자.

양의 정수로 이루어진 수열 $a = \langle a_1, a_2, \ldots, a_k \rangle$를 생각하자.

$f(a, x)$를 $a$에서 $x$가 나타나는 횟수로 정의하자. 예를 들어 $f(\langle 1, 4, 1, 1 \rangle, 1) = 3$이다.

$c(y)$를 $y$의 이진 표현에서 1의 개수로 정의하자. 예를 들어 $c(13) = c(1101_2) = 3$이다.

$b(a) = \sum \limits_{i \in a} c(f(a, i))$로 정의하자. 예를 들어 $b(\langle 1, 4, 1, 1 \rangle) = c(3) + c(1) = 2 + 1 = 3$이다.

주어진 $n$에 대해, $\sum \limits_{i=1}^{k} a_i = n$을 만족하는 모든 수열 중에서 $b(a)$의 최댓값을 구하자.

무엇이라고 답하겠는가?

첫째 줄에 정수 $t$가 주어진다. ($1 \le t \le 10^3$)

다음 $t$개 줄에 각각 정수 $n$이 하나씩 주어진다. ($1 \le n \le 10^{18}$)

각 테스트 케이스에 대해 입력 순서대로 답을 한 줄에 하나씩 출력한다.

첫 번째 예제에서 $b(a) = 3$을 만족하는 수열의 예로 $a = \langle 1, 4, 1, 1 \rangle$이 있다.