## FIBHARD - Hard Fibonacci

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

**is in the**

*N***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 ≤
≤ 10*N*^{15000000} - 1 ≤
≤ 100*T*

### 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 |