問題文

Carol は特殊なすごろくをしようとしている。

$1$ から $N$ の番号がふられている一直線に並べられている $N$ 個のマスがある。
$1$ から開始のマスとして、ゴールは $N$ が書かれているマスとする。

その場に書かれている数字の2進数で表現した時の $1$ のビット数 だけ「前」に進むことができる。
($1$ 未満と $N+1$ 以上のマスには移動することは出来ない、正確に $N$ にならないとゴールできない）

正整数 $N$ を与えられた時、ゴールに到達できる最短の移動数（開始のマスへも移動にカウントする）を求めてください。
到達できない場合は $\verb|-1|$ を出力してください。

入力

$N$

$1 \leq N \leq 10^{12}$

出力

最短の移動数、または $\verb|-1|$

サンプル

3

3

71623783

5691592

1000000000000

-1

例えば，$N$ が十分大きい時は次のように進むしかありません．

移動数   1  2  3  4  5  6  7  8  9 ...
マス     1  2  3  5  7 10 12 14 17 ...