問題

背景

ゲーム研究者のビッグブリッジ伯爵は、SOUND VERTEX III - GRAPH WARS というゲームの乱数生成にLFSR (日本語版 Wikipedia) という乱数生成方式が使われていることを発見した。 合法的にチートをする最高のパフォーマンスを発揮するために、乱数生成器の内部状態が特定の値となるタイミングを知りたい。

課題

三つの非負整数A, B, Xが与えられる。 0 以上の任意の整数 t に対して、乱数生成器の時刻 t での内部状態 a_t は次の式で与えられる。

• a_0\ =\ A
• a_{t+1}\ =\ (a_t\ /\ 2)\ \^\ (a_t\ %\ 2\ \times\ B)

ただし、" \times ", "/", "%"はそれぞれ整数での乗算, 除算, 剰余算、"^"は二進数表現でのビットごとのxor演算を表す。

a_t = X となる最小の t を出力せよ。 そのような t が存在しない場合は -1 を出力すること。

配点

300

入力

入力は以下の形式で与えられる。

A B X

制約

• 0 ≤ A, B, X < 2^{36}

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 0 ≤ A, B, X < 2^{10}

出力

a_t = X となるような最小の t を一行で出力せよ。

---

入力例1

7 6 5

出力例1

1

a_0 = 7, a_1 = (7 / 2) \^ 6 = 5 なので t = 1 となる。

---

入力例2

9 6 1

出力例2

2

a_0 = 9, a_1 = 2, a_2 = 1 である。

---

入力例3

3 4 6

出力例3

2

---

入力例4

8 7 6

出力例4

-1