D. Фибоначчи нийлбэрүүд

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

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

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

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

Фибоначийн тоонууд нь дараах дүрмийг хангана:

$F_1=1$

$F_2=2$

$F_i=F_{i-1}+F_{i-2},\ i>2$.

Хоосон биш $S=${$s_1,\ s_2,...,\ s_k$} өөр өөр фибоначчийн тоонуудаас бүрдсэн олонлог байг. Олонлогийн нийлбэр нь: Alt text байх $S$ олонлогийг $n$-ий задрал фибоначчи нийлбэр гэе.

Дараах хэдэн тоонууд задрал фибоначчи нийлбэр болохыг хялбар харж болно. Жишээ нь: бидэнд $13$ байг. $13:${$5,\ 8$}, {$2,\ 3,\ 8$}, {$13$} гэсэн гурван задралтай. Харин $16$-ийн хувьд $16:${$3,\ 13$}, {$1,\ 2,\ 13$}, {$3,\ 5,\ 8$}, {$1,\ 2,\ 5,\ 8$} гэсэн дөрвөн задралтай.

$n$ тоо өгөгдсөн бол боломжит ялгаатай задрал нийлбэрийн тоог ол.

Оролт

Эхний мөрөнд нийт тестийн тоо $t (1≤t≤10^5)$. Дараах $t$ мөрөнд $n (1≤n≤10^{18})$ тоо байрлана.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Тест бүрийн хувьд харгалзах хариуг нэг нэг мөрөнд хэвлэнэ.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Говьхүү

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

Оролт
2
13
16
Гаралт
3
4

Тэмдэглэл

Two decompositions are different if there exists a number that is contained in the first decomposition, but is not contained in the second one. Decompositions that differ only in the order of summands are considered equal.

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