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