B. Хос тоо

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бидэнд $(a, b)$ хос тоо байгаа. Бидэнд өгөгдсөн $(a, b)$ хосоос ($a+b, b$) эсвэл ($a, a+b$) хосуудыг нэг алхамаар гаргаж авч чадна. Анх $(1,1)$ хос өгөгдсөн байна. Таны даалгавар бол $к$ тоог олох ба энэ нь $(1,1)$ хосыг аль нэг тоо нь $n$ тоотой тэнцүү болтол хувиргах хамгийн бага алхамын тоо юм.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^6$) тоо өгөгдөнө.

Гаралт

Зөвхөн $k$ тоог хэвлэнэ үү.

Орчуулсан: Адъяа

Жишээ тэстүүд

Оролт
5
Гаралт
3
Оролт
1
Гаралт
0

Тэмдэглэл

The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1) $ -> $ (1,2) $ -> $ (3,2) $ -> $ (5,2).

Сэтгэгдлүүдийг ачааллаж байна...