비트 개수 (Large)

$f(x)$를 $x$를 2진법으로 나타냈을 때 등장하는 1의 개수로 정의한다. 예를 들어 5는 2진법으로 $101_2$이므로 $f(5) = 2$다.

양의 정수 $N$이 주어진다. $a + b = N$을 만족하는 0 이상의 정수 쌍 $(a, b)$ 가운데 $f(a) + f(b)$가 최대가 되는 쌍을 찾고, 그때의 $f(a) + f(b)$ 값을 출력한다.

첫째 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각 테스트 케이스의 $N$이 한 줄에 하나씩 주어진다.

제한

• $1 \le T \le 1000$
• $1 \le N \le 10^{18}$ ($N$은 32비트 정수형에 들어가지 않는다)

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: P

$X$는 1부터 시작하는 테스트 케이스 번호이고, $P$는 $f(a) + f(b)$의 최댓값이다.