就玩原神队的三人有一人跑出去玩了，剩下的两人还在酒店……

谦神找袁神玩原神，袁神以为谦神要玩袁神，谦神怒让袁神一边自己玩袁神去，然后谦神自己玩原神去了。

谦神想到前几天袁神提过的问题，便给了袁神一个整数 $n$ 让袁神自己一边从 $1$ 数到 $n^{n!}$ 去。然后这就被 pwp 挂到了 oj 上变成了题目。

不过这道题不要求你从 $1$ 输出到 $n^{n!}$，而是直接输出 $(n!)^{n!} \bmod 998244353$。

第一行输入一个整数 $T$ 表示样例数。（$1 \le T \le 5000$）

接下来每个样例一行输入一个整数 $n$。（$1 \le n \le 5000$）

对于每个样例，输出一行一个整数表示答案。