#FIBHARD. Hard Fibonacci

Hard Fibonacci

The problem author is not a very nice person. He wants you to calculate the Nth fibonacci number, which is defined as:

Fibonacci formula

Because the author is not very nice, the size of N can be huge, really huge. The exact size of N is in the Constraints section.

Input

The first line contains a single integer T, the number of test cases.

The next T lines contain a single integer N.

Output

For each of the T lines, output the Nth fibonacci number, modulo 998244353.

Example

Input:
5
0
1
1234
345639696828452375
419384601238473729475639183948326177846782649592628790267300203877
Output:
0
1
4936310
213237811
389871463

Constraints

  • 0 ≤ N ≤ 1015000000
  • 1 ≤ ≤ 100

Notes

  • The size of the file will not exceed 15MB.
  • Fast input may be required.
  • Fast languages like C / C++ are recommended.