题目背景

$\text{\textcolor{66CCFF}{兜兜转转再趟一遍人间}}$

$\text{\textcolor{66CCFF}{再同}\textcolor{EE0000}你\textcolor{66CCFF}{看那弯旧月}}$

题目描述

$\text{\textcolor{66CCFF}{1}}$ 和 $\text{\textcolor{EE0000}{0}}$ 正在玩一个数字游戏。

游戏开始时，$\text{\textcolor{EE0000}{0}}$ 会选择一个 $n$，然后把 $1,\ldots,2^n-1$ 这些数依次顺时针摆在一个环上，即 $1$ 的下一个是 $2$，$2$ 的下一个是 $3$，等等……$2^n-2$ 的下一个是 $2^n-1$，$2^n-1$ 的下一个是 $1$。$\text{\textcolor{EE0000}{0}}$ 把这样的环叫作『相思环』。

随后，$\text{\textcolor{66CCFF}{1}}$ 会开始对这个环进行若干次操作，每次操作后这个环上每一个位置的数会变成操作前这个位置的数和这个位置顺时针方向下一个位置的数的异或和。（请注意，如果 $2^n-1 = 1$，则这两个位置是相同的。）

$\text{\textcolor{66CCFF}{1}}$ 发现了经过若干次操作后，环上的数可能会恢复到一开始的情况。这时，如果继续操作，就会进入循环。定义像这样的能够回到初始状态的最小循环节称为『循』。$\text{\textcolor{66CCFF}{1}}$ 想知道对于给定的 $n$，是否存在『循』，如果存在那『循』的长度（循环节的长度，即使得环第一次恢复原始的『相思环』状态的操作数）又是多少。由于『循』的长度可能很大，请对 $998244353$ 取模。

输入格式

由于 $\text{\textcolor{66CCFF}{1}}$ 和 $\text{\textcolor{EE0000}{0}}$ 会玩很多次游戏，本题有多组测试数据。

第一行输入一个整数 $T$，代表测试数据组数。

接下来输入 $T$ 行，每行输入一个正整数 $n$，含义如题所述。

输出格式

输出共 $T$ 行。

对于每组测试数据，如果此时不存在『循』，输出一行 NO。

否则，输出一行一个整数，表示『循』的长度，对 $998244353$ 取模。

5
1
2
20120712
20150412
20250128

NO
3
788789717
987818393
932136822

提示

【样例解释】

以下将用序列来表示环。序列上的数在环上依次沿顺时针方向排布，序列的第一个位置为开始时『相思环』上数 $1$ 所在的位置。

对于样例的第一组测试数据，$n=1$，环大小为 $2^n-1=1$，其随操作的变化为 $\{1\}\to\{0\}\to\{0\}\to \ldots$，无法变回起始状态，不存在『循』，故输出 NO。

对于样例的第二组测试数据，$n=2$，环大小为 $2^n-1=3$，其随操作的变化为 $\{1,2,3\}\to\{3,1,2\}\to\{2,3,1\}\to\{1,2,3\}\to\ldots$，在 $3$ 次操作后回到原始状态，形成循环，故『循』的长度为 $3$，输出 $3 \bmod 998244353 = 3$。

【数据范围】

记 $N$ 为单一测试点的所有测试数据的 $n$ 的最大值。

对于所有测试点，有：

• $1 \le T \le 5 \times 10^5$；
• $1 \le N \le 10^9$。

每个测试点的具体数据范围见下表。 ::cute-table{tuack} |测试点编号|$T \le$|$N \le$| |:---:|:-----:|:-:| | $1$ | $100$ | $3$ | | $2$ | ^ | $15$ | | $3$ | $5 \times 10^5$ | ^ | | $4\sim5$ | $100$ | $5 \times 10^5$ | | $6\sim10$ | $5 \times 10^5$ | $10^9$ |