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 accomodate only a single person.
Given the size of palace N one has to find total number of ways people can be accomodatede in that.

Input

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

Output

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

Example

Input:
1
3
Output:
16