乘积

题号：NC53630
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

记 $\begin{matrix}A_i=(00..0\underbrace{11..1})_2\\\quad\quad\quad\quad i个1\end{matrix}$ ，即二进制表示下后i位为1，其余位为0的数。给定一个正整数n，求 $\prod_{i=1}^n\prod_{j=1}^nA_i\& A_j$ 。
输出答案对998244353取模后的结果。T组数据。

输入描述:

第一行一个整数T，表示数据组数。
接下来T行每行一个整数n，含义如题目描述所示。

输出描述:

输出T行，表示每次询问的结果。

示例1

输入

复制

2
2
4

输出

复制

3
1250235

备注:

。