There is a big palace in which rooms are constructed in the from of a square matrix. Now these rooms have to be filled with people.

As there are conflicts between people to maintain the equilibrium total number of people must be odd in every row and every column.

A room can accommodate only a single person.

Given the size of palace N one has to find total number of ways people can be accommodated.

Input

First line consists of an integer K and then K test cases follow.

Output

For each test case you have to output the result%98777 in a separate line.

Example

Input:
1
3
Output:
16