题目描述

对于一个排列 $P$,定义 $f(p)$:

给定一个整数 $n$ ,对于所有可能的长度为 $n$ 的排列 $P'$ ,计算 $\sum (f(P'))^3$ ,答案对 $998244353$ 取模

输入格式

第一行是一个整数 $T$ $(1 \le T \le 10^5)$，即测试用例的数量。

对于每组输入数据，输入一个正整数 $n$ $(1 \le n \le 5 \times 10^5)$

输出格式

对于每组数据，输出一个整数，表示答案

样例

2
3
3741

53
805156151