警匪游戏

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

农场里有 $N$ 头奶牛。每头奶牛必须且只能扮演“警察”或“小偷”中的一个角色，并且两个阵营都至少有一头奶牛。

每头奶牛都有一个非负整数合作指数。一个阵营的团队合作指数定义为该阵营内所有奶牛合作指数的按位与。

请计算有多少种角色分配方案，使警察阵营与小偷阵营的团队合作指数相等。只要至少一头奶牛扮演的角色不同，就认为两种方案不同。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据，第一行包含一个整数 $N$；第二行包含 $N$ 个非负整数 $A_1,A_2,\ldots,A_N$。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的分配方案数对 $998244353$ 取模后的结果。

样例输入 1

2
3
3 3 3
3
1 2 3

样例输出 1

6
0

样例解释

第一组数据中三个合作指数都等于 $3$，任意非空且非全部奶牛的警察集合都合法，共有 $6$ 种方案。第二组数据不存在合法方案。

数据范围

对于所有数据，$1\le T\le 5$，$1\le N\le 5\times 10^5$，$0\le A_i\le 2^{20}-1$。单个输入文件内所有测试数据的 $N$ 之和不超过 $10^6$。