Problem Description

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$.

Input Format

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 Format

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

2
2
3

2
-1

Hint

"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