C. Master of Both IV
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Prof.Chen is the master of arithmetic operations and binary operations. Today's homework for his students, Putata and Budada, is to find the number of non-empty subsequences $$$\{i_1,i_2,\dots,i_m\}$$$ ($$$1\leq i_1 \lt i_2 \lt i_3\dots \lt i_m\leq n,1\leq m\leq n$$$) of sequence $$$\{1,2,\dots,n\}$$$ satisfying that $$$\forall x\in[1,m],a_{i_x}|\bigoplus\limits_{j=1}^m a_{i_j}$$$, where $$$\{a_n\}$$$ is a given sequence.

Here $$$\oplus$$$ means bitwise exclusive-or operation, $$$\bigoplus\limits_{j=1}^m a_{i_j}$$$ equals to the bitwise exclusive-or of all elements $$$a_{i_j}$$$ for $$$1\leq j\leq m$$$. We say $$$x|s$$$ if and only if there exists an non-negative integer $$$k$$$ such that $$$s=k\cdot x$$$.

Please help Putata and Budada finish their homework. In order to ruin the legends, please output the answer modulo $$$998\,244\,353$$$.

Input

The first line contains one integer $$$t$$$ ($$$1\leq t\leq 2\cdot 10^5$$$), denoting the number of test cases.

For each test case, the first line contains one integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$), denoting the length of the sequence.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is $$$a_i$$$ ($$$1\leq a_i\leq n$$$), denoting the $$$i$$$-th element in the sequence. It is possible that $$$a_i=a_j$$$ for $$$i\neq j$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output one integer in one line, denoting the answer.

Example
Input
2
3
1 2 3
5
3 3 5 1 1
Output
4
11