AND Palindromes

 You are given an array 

A$A$ consisting of N$N$ integers. Calculate the number of ways to divide this array into subsegments, such that the sequence formed by taking bitwise AND in each segment of the partition is a palindrome.

A partition is palindromic if Bi=Bk+1−i$B_i=B_{k+1-i}$ for every 1≤i≤k$1\le i\le k$. Your task is to calculate the number of palindromic partitions. Since this number can be large, calculate it modulo 998244353$998244353$.

Input Format

• The first line of input contains T$T$ — the number of test cases you need to solve.
• The first line of each test case contains one integer N$N$ — the size of the array.
• The second line of each test case contains N$N$ space-separated integers A1,…,AN$A_1,\dots ,A_N$ — the elements of the array A$A$.

Output Format

For each test case, output on a new line the number of ways to partition A$A$ into subsegments, such that the bitwise AND of these segments form a palindrome.

Constraints

• T≤1500$T\le 1500$
• 2≤N≤3000$2\le N\le 3000$
• Sum of N$N$ over all test cases is at most 3000$3000$.
• 0≤Ai<230$0\le A_i<2^{30}$

Sample Input 1 

3
3
1 1 1
4
3 4 5 6
5
1 1 0 1 0

Sample Output 1 

4
1
4

Explanation

Test case 1$1$: The palindromic partitions are {[1,3]},{[1],[2,3]},{[1,2],[3]},{[1],[2],[3]}$\{[1,3]\},\{[1],[2,3]\},\{[1,2],[3]\},\{[1],[2],[3]\}$. To see why:

• For {[1,3]}$\{[1,3]\}$, B=[A1∧A2∧A3]=[1]$B=[A_1\wedge A_2\wedge A_3]=[1]$
• For {[1],[2,3]}$\{[1],[2,3]\}$, B=[A1,A2∧A3]=[1,1]$B=[A_1,A_2\wedge A_3]=[1,1]$
• For {[1,2],[3]}$\{[1,2],[3]\}$, B=[A1∧A2,A3]=[1,1]$B=[A_1\wedge A_2,A_3]=[1,1]$
• For {[1],[2],[3]}$\{[1],[2],[3]\}$, B=[A1,A2,A3]=[1,1,1]$B=[A_1,A_2,A_3]=[1,1,1]$

Clearly B$B$ is a palindrome in all 4$4$ cases.

Test case 2$2$: The only palindromic partition is {[1,4]}$\{[1,4]\}$.

Test case 3$3$: The palindromic partitions are {[1,3],[4,5]},{[1,3],[4],[5]},{[1,4],[5]},{[1,5]}$\{[1,3],[4,5]\},\{[1,3],[4],[5]\},\{[1,4],[5]\},\{[1,5]\}$.