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
Dla danego N, podaj wartość N-tej liczby Fibonacciego modulo 10000 (czyli resztę z dzielenia przez 10000).
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).
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.
5 2 4 8 40 1
1 3 21 4155 1