A46941.偶数Ⅰ

注:本题与偶数Ⅱ题面相同，只有数据范围不同。

我们定义一个正整数的"美丽度"为该正整数转换为二进制表示后末尾连续 $0$ 的个数。例如，正整数 $4$ 转换为二进制是 $100$，所以它的美丽度为 $2$。

现在，我们引入一个函数 $f(a, b, c)$，其定义如下：

$$f(a, b, c) = \left| a^c - b^c\right|$$

有趣的是，我们发现通过这个函数，可以将三个奇数的运算结果变为偶数。

最近，Alice 听闻你在数学方面造诣颇深，于是她向你求助，希望你能帮忙解决这样一个问题：从前面 $n$（$n\in \mathbf{N}^*$ 且 $n \geq 3$）个正奇数中任意选取三个互不相同的数 $a$、$b$、$c$ ，求 $f(a, b, c)$ 的美丽值的期望值。

每个测试输入包含多个测试用例。输入的第一行包含一个正整数 $t$ ，表示测试用例的组数。测试用例的描述如下：

每个测试用例的唯一一行包含一个正整数 $n$ ，$n$ 的意义见题目描述。

对于每个测试用例，打印一个单一的整数，即 $p\cdot q^{-1}\mod 998244353$ 的值。

数据范围

• $1\le t\le 3 \times 10^3$
• $3\le n\le 3 \times 10^3$

经过严谨的数学证明可知，该期望值的答案能够表示为最简分数形式 $\dfrac{p}{q}$，其中 $p$ 和 $q$ 均为整数，并且 $q$ 满足 $q\not\equiv 0\pmod{998244353}$。请你计算并输出一个满足 $p\cdot q^{-1}\mod 998244353$ 的整数。也就是说，输出一个整数 $x$，使得 $0\leq x\lt 998244353$ ，并且 $x\cdot q\equiv p\pmod{998244353}$。

提示：依据费马小定理，有 $q^{-1}\equiv q^{998244351}\pmod{998244353}$。

样例解释:
当 $n$ 的值为 $3$ 时。 $(a,b,c)$ 的组合一共有 6 种。如 $(1 , 3 ,5)$ , $(1 ,5 ,3 )$ , $(3,1,5)$ , $(3,5,1)$ , $(5,3,1)$ , $(5,1,3)$ ,他们通过函数进行计算的结果分别为 $242$ ,$124$ , $124$ , $2$ , $2$ , $124$ ,其美丽值的分别为 $1$ , $2$ , $1$ , $1$ , $1$ , $2$ 。因此美丽值的期望为 $\dfrac{4}{3}$ ，进行相应的运算之后为 $332748119$ 。