Bit Count (Small)

Let $f(x)$ be the function that returns the number of ones in the binary representation of $x$. For example, 5 is written as $101_{(2)}$ in binary, so $f(5) = 2$.

You are given a positive integer $N$. Among all pairs of integers $a, b \ge 0$ with $a + b = N$, find a pair that maximizes $f(a) + f(b)$ and print that maximum value.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one positive integer $N$.

Constraints

• $1 \le T \le 1000$
• $1 \le N \le 10^{18}$

For each test case, print one line in the following form.

Case #X: P

Here $X$ is the test case number starting from 1, and $P$ is the maximum value of $f(a) + f(b)$.