Let us define sequences similar to those of Collatz with two parameters x and y. Given a number n, the algorithm to get the next number is:

- if n is even, we move to n/2 + x;
- otherwise, we move to 3n + y.

The standard Collatz sequence corresponds to x = 0 and y = 1.

Given x, y and a starting number n, compute the length of the cycle reached by applying the above algorithm. For example, if x = 1, y = 5 and n = 8, then the defined sequence is 8, 5, 20, 11, 38, 20, 11, 38, … so the cycle has length 3.

Since numbers can become very large,
and we have no mathematical guarantee that we will reach a cycle,
we will stop if at some point the sequence reaches a number greater than 10^{8}.

Input

Input consists of several cases,
each with three natural numbers x, y and n.
Assume that both x and y do not exceed 1000,
that y is odd (for the sequence to have some interest),
and that the initial n is not larger than 10^{8}.

Output

For every case,
print the length of the cycle,
or the first number that strictly exceeds 10^{8}.

Observation

Take into account that the sequences usually reach fast a “short” cycle.

Public test cases

**Input**

1 5 8 0 5 0 10 11 3 7 3 6 1 999 100000000 433 805 215476 0 1 33333333

**Output**

3 1 1 35 150001002 490 3

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python