题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，初始时 $a_i=i$。对该序列进行 $n-1$ 次操作，其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$，令 $a_j$ 变为 $a_j+2a_{n-i+1}$。

求操作完毕后 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。

输入格式

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

接下来 $T$ 组数据，每组一行一个正整数 $n$ $(1\leq n\leq 10^9)$，表示序列的长度。

输出格式

$T$ 行，每行一个整数表示 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。

3
4
2
5

30
5
55

3
4
3
5

30
14
55

3
8
1
3

204
1
14