비트 개수 (Small)

시간 제한5초메모리 제한512 MB

요약

N을 음이 아닌 두 정수 a와 b의 합으로 나누어 a와 b의 이진수에 들어 있는 1의 개수 합이 가장 커지는 값을 구합니다.

문제

$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$ 이 하나씩 주어진다.

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

Case #X: P

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

예제 1

입력

4
1
4
31
1125899906842624

예상 출력

Case #1: 1
Case #2: 3
Case #3: 5
Case #4: 51