京都大学プログラミングコンテスト2015

H - Bit Count


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

正整数 X を二進数で表したときに出現する 1 の個数を, X のビットカウントという.

与えられる正整数 N について, XX + N のビットカウントが等しくなるような正整数 X は存在するだろうか?

存在するならばその最小値を,存在しないなら -1 を出力せよ.


入力

入力は以下の形式で標準入力から与えられる.

T
N_1
:
N_T
  • テストケースの数は T ( 1 \leq T \leq 100 ) であり, i ( 1 \leq i \leq T ) 番目のテストケースは N_i ( 1 \leq N_i \leq 10^{16} ) である.
  • 入力値はすべて整数である.
  • 各々の出力の値はそれぞれ 100 桁を越えないことが保証されている.

出力

出力は T 行からなる. i 行目の出力は, N_i についての答えである.


入力例

3
10
20
30

出力例

10
20
2

Source name

京都大学プログラミングコンテスト2015

Submit提出する