12458번 - ビット数 (Large) 다국어

f(x) を 「x を 2進数表記した時の "1" の個数を返す関数」と定義します。 例えば、5 は 101₂ と 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 ≤ 10¹⁸ (32bit整数型には収まらないことに注意)

各テストケースごとに、

Case #X: P

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