U551228 齐国芒果的矩阵

晓梦非常好奇的问齐国芒果，我们都开始学习矩阵快速幂了，是不是已经超越大学生了。 这个问题齐国芒果表示无法回答。 为此，他提出了一道特殊的矩阵题目，考察大家的知识点掌握情况，耐心看完，会发现和某些数学小游戏（比如数独）非常类似。 齐国芒果需要你构建一个特殊的矩阵 $AS$，大小是 $n \times n$ 的，这个矩阵满足很多的性质条件： * 矩阵内部的所有元素都是 $AS \in \{0, 1, 2\}$。 * 矩阵是一个对称矩阵，也就是 $AS[i][j]$ = $AS[j][i]$。 * 矩阵内部的元素满足 $\sum_{j = 1}^{j = n}AS[i][j] = 2$ 对所有的 $i$ 都是适用的。 * 矩阵内部对称轴上的元素 $AS[i][i]$ 始终都是等于 $0$。 请你帮助晓梦快速解答有多少个这样的矩阵满足条件，答案可能会非常大，请直接对 $99824353$ 取模。

第一行输入包含一个整数 $t$ ， 表示当前的测试组数。 接下来 $t$ 行， 每行包含一个正整数 $n$ ， 表示矩阵的大小。

输出包含 $t$ 个整数，表示每组测试取模之后的最终方案数量。

### 样例一解释 当 $n = 2$ 的时候 $$ AS = \begin{bmatrix} 0 & 2 \\ 2 & 0 \end{bmatrix} $$ 当 $n = 3$ 的时候 $$ AS = \begin{bmatrix} 0& 1 & 1 \\ 1 & 0 & 1\\ 1 & 1 & 0 \end{bmatrix} $$ 对于 $30 \%$ 的数据范围， 满足 $1 \le t \le 5, 1 \le n \le 8$。 对于 $100 \%$ 的数据范围， 满足 $1 \le t \le 10^3, 1 \le n \le 10 ^ 5$。