题目描述

给定 $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}$。