RoboContest

Xotira 16 MB Vaqt 1000 ms

14

Fibonacci Total

Fibonacci ketma ketligi:

$F_1 = 1$ ,
$F_2 = 2$ ,
$F_i = F_i -_1 + F_i -_2, i > 2$ .

Shu ketma-ketlik asosida fibonacci hadlarini ko'rib chiqing va $S = \{s_1, s_2, ..., s_k\}$ ushbu to'plam elementlari yigindisini toping.

$\displaystyle\sum_{I=1}^{K} S_i=n$

Sizning vazifangiz $n$ soni uchun fibonacci sonlaridan iborat bo'lgan nechata ketma-ketlik tuzish mumkin ekanligini topishdan iborat.

Kiruvchi ma'lumotlar:

Kiritish faylida Birinchi qatorda testlar soni $t(1 ≤ t ≤ 10^5)$

Har bir test uchub alohida qatorlarda $n (1 ≤ n ≤ 10^{18})$ butun soni kiritiladi.

Agar siz C++ da bolsangiz, Raqamlarni o'qish yoki yozish uchun %lld spesifikatsiyasidan foydalaning. Tavsiya etilgan oqimlar cin, cout yoki %I64d spetsifikatsiyasi.

Chiquvchi ma'lumotlar:

Chiqish faylida alohida qatorlarda har bir test uchun javobni chiqaring.

Misollar

#	input.txt	output.txt
1	2 13 16	3 4

Izoh:

1-test:

n = 13 uchun, S = {13, 5 + 8, 2 + 3 + 8} ketma-ketlik tuzish mumkin.
n = 16 uchun, S = {3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8} ketma-ketlik tuzish mumkin.

Eslatma:

Agar to'plamda boshqa tuzilgan toplamdagi sonlardan 1 ta bolsa ham farqli son bolsa bu to'plam boshqalaridan farqlanadi. Faqat toplamlardagi sonlarni o'rni almashib kelsa ham ular 1 ta deb hisoblanadi.

RoboContest

Masala N

Fibonacci Total