Sesja

Liczby Fibonacciego, to taki ciąg, ktorego pierwszy wyraz to 0, drugi to 1 a każdy następny jest sumą dwóch poprzednich wyrazów. Kilka początkowych wyrazów ciągu to: 0,1,1,2,3,5,8,... Napisz program, który wypisze n-tą z kolei liczbę Fibonacciego, gdzie n jest liczbą całkowitą i 0 <= n <= 10000.

Wejście:

Na wejściu mamy liczbę całkowitą a <=100 zakończona znakiem nowej linii, będącą liczbą powtórzeń serii danych.Następnie w każdym przypadku testowym wpisujemy numer z kolei n-tej liczby Fibonacciego, 0 <= n <= 10000, którą chcemy wypisać.

Wyjście:

N-ta Liczba całkowita Fibonacciego, będąca odpowiedzią na każdy przypadek testowy.

Przykład

Wejście:
4
3
6
7
10
Wyjście:
1
5
8
34

---

Wskazówka:

Zastosować algorytm dynamiczny (tablica), ze względu na szybką obsługę zapytań.