[LSOT-2] Tree and Xor

tyr 很唐。

给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\bigoplus\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \sim fa_n$ 的字典序最小。其中，$\oplus$ 表示异或运算。 其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。 你需要输出 $\sum\limits_{i=2}^ni \times fa_i$，若无解则输出 $-1$。

第一行，一个正整数 $T$，表示询问数量。 接下来每 $T$ 行每行一个正整数 $n$ 表示一次询问。

一共 $T$ 行，每行一个整数表示答案除 $998244353$ 的余数。

2
2
3

2
-1

**「本题采用捆绑测试」** - $\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$，其中 $k$ 是自然数。 - $\texttt{Subtask 5(50 pts)：}$无特殊限制。 对于所有数据，$1\le T\le 10^6$，$2 \leq n \leq 10^{9}$。