시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 1 1 1 100.000%

문제

f(x) を 「x を 2進数表記した時の "1" の個数を返す関数」と定義します。 例えば、5 は 1012 と 2 進数表記されるので、f(5) = 2 です。

正の整数 N が与えられるので、 a + b = N を満たす 0 以上の整数 a, b の組の中で f(a) + f(b) が最大になるものを求め、その時の f(a) + f(b) の値を出力してください。

입력

最初の行はテストケースの個数 T を表す正の整数です。 各テストケースは1行の文字列で表現され、それぞれの行には N を表す正の整数が1つだけ含まれています。

制約

  • 1 ≤ T ≤ 1000
  • N ≤ 1018 (32bit整数型には収まらないことに注意)

출력

各テストケースごとに、

Case #X: P

という内容を1行出力してください。ここで X は 1 から始まるテストケース番号、P は f(a) + f(b) の最大値です。

예제 입력 1

4
1
4
31
1125899906842624

예제 출력 1

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

채점

  • 예제는 채점하지 않는다.