B. 按位或
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

定义一个长度为$$$n$$$的数组 $$$a_1,a_2,\cdots,a_n$$$ 是好数组当且仅当 $$$\forall{i}\in[1,n),~a_1~|~a_2|~\cdots~|a_i~=~a_{i+1}~|~\cdots~|~a_n$$$。其中$$$|$$$表示按位或运算。

小文有一个长度为$$$n$$$的数组 $$$a_1,a_2,\cdots,a_n$$$，他想知道有多少个不同的$$$1$$$到$$$n$$$的排列 $$$p_1,p_2,\cdots,p_n$$$，使得 $$$a_{p_1},a_{p_2},\cdots,a_{p_n}$$$ 是一个好数组。

满足条件的排列数量可能会很大，你只需要输出其对 $$$998244353$$$ 取模后的结果即可。

Input

第一行输入一个整数 $$$t~(1\leq{t}\leq{10^5})$$$ 表示有$$$t$$$组样例。

每一个样例的第一行输入一个整数$$$n~(2\leq{n}\leq{2\cdot{10^5}})$$$。

每一个样例的第二行输入$$$n$$$个整数 $$$a_1,a_2,\cdots,~a_n(1\leq{a_i} \lt 2^{30})$$$。

数据保证所有样例的$$$n$$$之和不超过 $$$2\cdot{10^5}$$$。

Output

对于每个样例输出一个整数，即满足条件的排列数对 $$$998244353$$$ 取模后的结果。

Example
Input
4
2
1 1
3
1 2 3
5
1 3 2 2 3
4
1000000000 5454135 1000000000 9985453
Output
2
0
12
0