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

Числа Фибоначчи определяется следующим образом:

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

Выходные данные

Для каждого теста выведите в отдельной строке соответствующее число Фибоначчи.

Примеры