FIBHARD - 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.

Added by:dingledooper
Date:2019-10-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-11-22 10:15:38 :D
Great problem. Learned something new.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.