Задачі
Число Фібоначчі
Число Фібоначчі
Визначимо числа Фібоначчі наступним чином:
F (1) = F (2) = 1
F (n) = F (n - 1) + F (n - 2) для n ≥ 3.
Обчислити n-те число Фібоначчі.
Вхідні дані
У першому рядку задано кількість тестів t (1 ≤ t ≤ 10^3
). У кожному з наступних t рядків міститься одне число n (1 ≤ n ≤ 10^4
).
Вихідні дані
Для кожного тесту виведіть в окремому рядку відповідне число Фібоначчі.
Приклад
Вхідні дані #1
5 1 2 3 4 5
Вихідні дані #1
1 1 2 3 5