题目描述

• 对于一个排列 $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)$。

输出格式

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

输入输出样例 #1

输入 #1

2
3
3741

输出 #1

53
805156151