# Collatz pseudo-sequences (2) P69781

Statement html

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 108.

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 108.

Output

For every case, print the length of the cycle, or the first number that strictly exceeds 108.

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