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 N_i, 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(N_i))).

Ograniczenia

1 ≤ Z ≤ 100 000, 1 ≤ N_i ≤ 10¹⁸.

Przykład

2
2
6

1
10946