The problem author is not a very nice person. He wants you to calculate the N^th 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.

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 N^th fibonacci number, modulo 998244353.

Example

Input:
5
0
1
1234
345639696828452375
419384601238473729475639183948326177846782649592628790267300203877

Output:
0
1
4936310
213237811
389871463

Constraints

• 0 ≤ N ≤ 10^15000000
• 1 ≤ T ≤ 100

Notes

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