题目描述

小红在黑板上写下了一个计算式，由 $n$ 个数字组成，数字之间用加号 + 连接：

现在，小蓝想擦掉黑板上的一些 +。

但是小蓝擦得不太干净，每次只能擦掉 + 中间的横线 -，这样 + 就会变成 |。

巧合的是，| 也是一种运算符。

例如：1 + 2 擦掉 + 的横线后会变成 1 | 2，其中 | 表示按位或运算。

小蓝想知道，有多少种不同的擦法，使得修改后的计算式与原来的计算式结果相同。

注意，不擦任何 + 也是一种方案。

特别地，本题中规定 | 的运算优先级高于 +。

两种擦法不同，当且仅当至少存在一个位置，在一种擦法中使用 +，而在另一种擦法中使用 |。

输入格式

第一行输入一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。

对于每组测试数据：

• 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数字的个数。
• 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^{31}$）。

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的不同擦法数量。

由于答案可能很大，请将答案对 $998244353$ 取模后输出。

输入输出样例

样例输入 #1

3
2
1 2
3
1 2 3
4
1 2 0 4

样例输出 #1

2
2
8

说明/提示

样例解释

• 第一组数据：
  原来的计算式为 $1 + 2$，有以下两种擦法：
  • 不擦 +，结果为 $1 + 2 = 3$；
  • 擦掉 + 的横线，变成 $1 | 2$，结果为 $3$。
    因此共有 $2$ 种方案。

按位或运算说明

按位或（OR）：将两个整数写成二进制形式，从右往左逐位进行计算。如果某一位中至少有一个数字是 $1$，那么这一位的结果就是 $1$；只有两个数字这一位都是 $0$ 时，结果才是 $0$。

例如：$1 | 2 = 3$，因为：

001
010

011

约束条件

• $1 \le T \le 10$
• $1 \le n \le 2 \times 10^5$
• $0 \le a_i < 2^{31}$
• 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$
• 所有输入值均为整数。