Masala #0073

Xotira 16 MB Vaqt 1000 ms

Fibonacci – oxirgi raqam

F₀ = 0, F₁ = 1, … , F_k = F_k-1 + F_k-2 (k > 1) sonlar ketma-ketligi Fibonacci ketma-ketligi deyiladi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida T(1 ≤ T ≤ 10⁵) testlar soni kiritiladi. Keyingi T ta qatorda bittadan butun son, N(0 ≤ N ≤ 10¹⁸) soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, har bir testdagi N uchun alohida qatorda N-fibonacci sonining oxirgi raqami chop etilsin.

Misollar

#	input.txt	output.txt
1	5 3 4 5 6 7	2 3 5 8 3
2	8 12 16 34 18 23 36 35 35	4 7 7 4 7 2 5 5