Problem description
Jasio postanowił pomóc w przerzucaniu zadań na nowy system Solve 4. W tym celu wybrał jedno z zadań znajdujących się w Solvie 3 i nieznacznie je zmodyfikował. Niestety, tak zmodyfikowane zadanie okazało się dla Jasia zbyt trudne, więc poprosił Cię o pomoc.
Twoim zadaniem jest obliczenie wartości Fib(Fib(Fib(N))), gdzie Fib(N) oznacza N-tą liczbę Fibonacciego.
W ramach przypomnienia, ciąg liczb Fibonacciego definiujemy zgodnie ze wzorem: Fib(0) = 0, Fib(1) = 1, Fib(N+2) = Fib(N+1) + Fib(N) dla N ≥ 0.
Jako że wynik może okazać się zbyt duży do pomieszczenia w znanym wszechświecie, wystarczy że wypiszesz jego resztę z dzielenia przez 998 244 353.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Z, będąca liczbą zestawów testowych.
W i-tym z kolejnych Z wierszy znajduje się jedna liczba naturalna Ni, będąca wartością, dla której należy obliczyć wynik.
Wyjście
W i-tym wierszu należy wypisać odpowiedź dla i-tego zestawu testowego.
Powinna być ona resztą z dzielenia przez 998 244 353 wartości Fib(Fib(Fib(Ni))).
Ograniczenia
1 ≤ Z ≤ 100 000, 1 ≤ Ni ≤ 1018.
Przykład
| Input | Output | Explanation |
|
|
Dla N = 2 mamy Fib(2) = 1 i Fib(1) = 1, zatem Fib(Fib(Fib(2))) = 1. Dla N = 6 mamy Fib(6) = 8, Fib(8) = 21 i Fib(21) = 10946, zatem Fib(Fib(Fib(6))) = 10946. |