Red Dragon Dew forwarded a picture of a Bingo game:
The above is an example of a $$$5\times 5$$$ Bingo game. For an $$$n\times n$$$ Bingo game, the player must read the description on each cell and check off all the cells that satisfy the description. If the checked cells form at least one line (horizontally, vertically, or along either of the two diagonals), then the player is considered to have succeeded in the game.
Now, Red Dragon Dew wants to know the maximum number of cells that can be checked while ensuring the player still fails. That task is too simple, so she further wants to know: how many different schemes are there for checking the maximum number of cells such that the player fails?
Specifically, if there is a cell that is unchecked in one scheme and checked in another, then the two schemes are considered different. To avoid excessively large outputs, the final answer is taken modulo $$$998244353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le 10$$$). The description of the test cases follows:
The only line of each test case contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$), which represents the size of the Bingo game.
For each test case, output the number of schemes for checking the maximum number of cells that (still result in failure), modulo $$$998244353$$$.
437114997
2 2004 293058554 136105176
Here is $$$3\times 3$$$ bingo game schemes for checking the maximum number of cells which still results in failure.
