#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

The 3n + 1 problem is overdone, and so this course empathizes with it.

But that is no excuse for laziness, as team portable orange energy (POE) has decreed. Therefore, this variant has a twist.

The task was to input a number n. If the number is even, divide it by 2. Otherwise, multiply it by 3, and add 1. Repeat this process until you get the number 1. The output was the number of times this process was repeated. eg if n is 3, the answer is 7.

However, this time there is another way to end the processes. Instead of the number having to reach 1 before stopping, the number can stop once it is a fibonacci number.

## Limits

0 < n < 100 000

30% - n < 1000

## Input

One integers, *n*.

## Output

The number of times the process was repeated.

## Sample Input

73

## Sample Output

3

## Explanation of sample case

73 -> 220 -> 110 -> 55 ==> Three steps

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 3 | 1s | 32MB | Minimum |

2 | 70 | 7 | 1s | 32MB | Minimum |

3 | 0 | 1 | 1s | 32MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o collatzoncemore -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512