Masala #0073

Xotira 16 MB Vaqt 1000 ms
14

Fibonacci – oxirgi raqam

F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2 (k > 1) sonlar ketma-ketligi Fibonacci ketma-ketligi deyiladi.


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida T(1 ≤ T ≤ 105) testlar soni kiritiladi. Keyingi T ta qatorda bittadan butun son, N(0 ≤ N ≤ 1018) 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