题目描述

对于一个排列 $P$，定义 $f(P)$ 如下：

function f(P):
    stack = []

    for element in P:
    while stack is not empty and stack.top() > element:
    stack.pop()
    stack.push(element)

    return the size of stack

给定一个整数 $n$，求所有长度为 $n$ 的排列 $P'$ 的 $(f(P'))^3$ 的和，对 $998244353$ 取模。

输入格式

本题有多组输入数据。

第一行输入一个正整数 $T(1 \leq T \leq 10^5)$，表示输入数据组数。

接下来的每组输入数据，输入一个正整数 $n(1 \leq n \leq 5 \cdot 10^5)$。

输出格式

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

2
3
3741

53
805156151