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

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

입력 형식

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

制約

• 1 ≤ T ≤ 1000
• N ≤ 10000

各テストケースごとに、

Case #X: P

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

예제 입력

4
1
4
31
1125899906842624

예제 출력

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