Число Фібоначчі

Визначимо числа Фібоначчі наступним чином:

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).

Вихідні дані

Для кожного тесту виведіть в окремому рядку відповідне число Фібоначчі.

Приклади