A46943.偶数Ⅱ

注:本题与偶数 $Ⅰ$ 题面相同，只有数据范围不同。
我们定义一个正整数的"美丽度"为该正整数转换为二进制表示后末尾连续 $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 10^6$
• $3\le n\le 10^6$

经过严谨的数学证明可知，该期望值的答案能够表示为最简分数形式 $\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}$。