宾果游戏

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

对于一个 $n\times n$ 的宾果游戏，玩家需要勾选部分单元格。如果被勾选的单元格至少形成一条完整的线（横向、纵向或两条对角线中的任意一条），就认为玩家在游戏中成功。

求在保证玩家仍然失败的前提下，勾选单元格数量达到最大时共有多少种不同方案。

如果某个单元格在一种方案中未被勾选，而在另一种方案中被勾选，则两种方案不同。答案对 $998244353$ 取模。

输入格式

第一行包含测试组数 $T$。

接下来每组测试仅一行，包含整数 $n$，表示宾果游戏的大小。

输出格式

对于每组测试，输出勾选最多单元格且仍然失败的方案数，对 $998244353$ 取模。

样例输入 1

4
3
7
114
997

样例输出 1

2
2004
293058554
136105176

样例解释

下面展示了 $3\times3$ 宾果游戏中两种勾选最多单元格但仍然失败的方案。

数据范围

• $1\le T\le10$；
• $2\le n\le10^5$。