P15790 「1&0OI R1」相思若循

> $\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$ 取模。

**【样例解释】** 以下将用序列来表示环。序列上的数在环上依次沿顺时针方向排布，序列的第一个位置为开始时『相思环』上数 $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$ |