P10157 [LSOT-2] Tree and Xor

Given $n$, you need to construct a rooted tree with $n$ nodes, rooted at $1$, such that $\bigoplus\limits_{i=1}^ndegree(i)=0$ and the sequence $fa_2 \sim fa_n$ is lexicographically smallest. Here, $\oplus$ denotes the XOR operation. Here, $degree(i)$ denotes the number of nodes connected to node $i$, $fa_i$ denotes the parent of node $i$, and $fa_i < i$. You need to output $\sum\limits_{i=2}^ni \times fa_i$. If there is no solution, output $-1$.

The first line contains a positive integer $T$, indicating the number of queries. In the next $T$ lines, each line contains a positive integer $n$, indicating one query.

Output $T$ lines in total. Each line contains one integer, the answer modulo $998244353$.

**"This problem uses bundled tests."** - $\texttt{Subtask 1(5 pts)：}n \leq 7$. - $\texttt{Subtask 2(10 pts)：} n \leq 20$. - $\texttt{Subtask 3(20 pts)：}\sum n \leq 2000$. - $\texttt{Subtask 4(15 pts)：}n = 2^k-1$, where $k$ is a natural number. - $\texttt{Subtask 5(50 pts)：}$No special constraints. For all testdata, $1\le T\le 10^6$, $2 \leq n \leq 10^{9}$. Translated by ChatGPT 5