Problem description


Fibonacci z utrudnieniem
(fibonacci-hard)
Memory limit: 64 MB
Time limit: 3.00 s

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
2
2
6
1
10946

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.