In one step, a pair of numbers (a, b) can be transformed into either (a, b + a^2) or (a + b^2, b).
Assume the starting pair is (1, 1).
What is the minimum number of steps required so that at least one of the numbers in the new pair becomes equal to n?
Input
A natural number n (1 \le n \le 10^{6}).
Output
Print the minimum number of steps required.
Examples
| standard input | standard output |
|---|
| 9
| 3
|
| 19
| 4
|
Note
Explanation for the first test case:
(1,1) \to (1,2) \to (5,2) \to (9,2)