001 - ビットすごろく

もんだいー

Carol は特殊なすごろくをしようとしている。 1からNの番号がふられている一直線に並べられているN個のマスがある。 1から開始のマスとして、ゴールはNが書かれているマスとする。 その場に書かれている数字の2進数で表現した時の1のビット数 だけ「前」または「後」に進めることができる。 (1未満とN+1以上のマスには移動することは出来ない、正確にNにならないとゴールできない） 自然数Nを与えられた時、ゴールに到達できる最短の移動数（開始のマスへも移動にカウントする）を求めてください。 到達できない場合は-1を出力してください。 開始のマスがすでにゴールになっている場合もあリます。

入力

N

マスの数 N(1≤N≤10000) が与えられる。

出力

最短の移動数、または　-1

---

入出力例

入力例1

5

出力例1

4

解説

1->2->3->5 という経路をたどります。

入力例2

11

出力例2

9

解説

1->2->3->5->7->10->8->9->11 という経路をたどると9移動数で到達します。

入力例2

4

出力例2

-1

解説

4つしかマスがないときは到達することは出来ません。