II Mistrzostwa Wielkopolski w Programowaniu Zespołowym 3-4 grudnia 2004
Zadanie P. Ciąg Fibonacciego

Opis

Ciąg Fibonacciego to ciąg liczb całkowitych, określonych rekurencyjnie w następujący sposób.

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2, dla n ≥ 2

Początkowe wyrazy ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

Zadanie

Dla danego N, podaj wartość N-tej liczby Fibonacciego modulo 10000 (czyli resztę z dzielenia przez 10000).

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych, które dalej pojawią się na wejściu. Każdy zestaw składa się z jednej linii, zawierającej dokładnie jedną liczbę całkowitą N (1 ≤ N ≤ 20000).

Specyfikacja wyjścia

Dla każdego zestawu danych na wyjściu należy wypisać, w osobnej linii, jedną liczbę całkowitą, będącą resztą z dzielenia FN modulo 10000.

Przykład

Wejście

5
2
4
8
40
1

Wyjście

1
3
21
4155
1