Description

现在 Cirno 手上有着 $T$ 天的作业，每天的作业可以用一个二元组 $( n, V )$ 表示，其中 $n$ 表示集合的大小， $V$ 表示大小为 $n$ 的集合. 现在，Cirno 需要求出的是 $V$ 的所有子集的异或和的和，答案对 $998\,244\,353$ 取模。

形式化地：

$$\text{ans}\equiv \sum_{S \subseteq V} \mathop{\bigoplus}\limits_{ s \in S } s \pmod {998\,244\,353}$$

Input Format

第一行，一个整数 $T$。

以下 $T$ 行，每行一个二元组 $( n, V )$。

Output Format

$T$ 行，每行一个整数，表示答案。

1
3 1 2 3

12

Hint

• Subtask 1（17pts）：$T, n \le 8$；
• Subtask 2（22pts）：$T, n \le 100$；
• Subtask 3（61pts）：$T, n \le 3\times10^6$。

对于 $100\%$ 的数据，$\sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$。