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:
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.
The first line contains a single integer T, the number of test cases.
The next T lines contain a single integer N.
For each of the T lines, output the Nth fibonacci number, modulo 998244353.
- 0 ≤ N ≤ 1015000000
- 1 ≤ T ≤ 100
- The size of the file will not exceed 15MB.
- Fast input may be required.
- Fast languages like C / C++ are recommended.