Ketma-ketlik G

1. Ketma-ketlik G

Bizga quyidagi ketma-ketlik berilgan bo’lsin. G(1) = 1, G(2) = 2, G(i)=G(i-2)+G(i-1), i > 2
Aniqlanishicha, har qanday musbat butun sonni ushbu ketma-ketlikning hadlari yordamida ifodalash mumkin ekan. Bunda bironta had takrorlanmaydi. Misol uchun 21 va 6 ni bir nechta holatlarini ko’rib chiqaylik.
21 uchun: 21, 13+8, 13+5+3, 13+5+2+1
6 uchun: 5+1, 3+2+1
Bu yerda 21ni minimal bitta G ketma-ketlikning hadi orqaliifodalashimiz mumkin ekan (chunki 21 ham shu ketma-ketlikning hadi). Maksimal 4 ta. Sizning vazifangiz berilgan n sonini minimal va maksimal nechta G ketma-ketlik hadi orqali ifodalash mumkinligini aniqlash!

Kirish: Bitta n soni beriladi 1 <= n <= 10**18.

Chiqish: Minimal va maksimal nechta had orqali ifodalash mumkinligini aniqlab, alohida qatorlarda chop eting.

Testlar:
Input output

1.

21. 
    1
    

4


2.

6. 
   2
   

3


3.

116. 
     4
     

7