Skaičių porą (a,b) vienu žingsniu galime paversti į porą (a,b+a^2) arba (a+b^2,b).
Tarkime, kad pradinė pora yra (1,1).
Kiek mažiausiai žingsnių reikia atlikti, kad bent vienas naujos gautos poros narys būtų lygus n?
Input
Natūralus skaičius n (1 \le n \le 10^{6}).
Output
Atspausdinkite mažiausią galimą žingsnių skaičių.
Examples
| standard input | standard output |
|---|
| 9
| 3
|
| 19
| 4
|
Note
Pirmo testo pavyzdys:
(1,1) \to (1,2) \to (5,2) \to (9,2)