You are given an array $$A$$ consisting of $$N$$ positive integers. Here, $$f(i, j)$$ is defined as the bitwise AND of all elements of the array $$A$$ after replacing all elements of $$A$$ in range $$[i, j]$$ (both inclusive) with $$(2^{25} - 1)$$. Your task is to find:
\(-f(1, N) + \sum\limits_{i=1}^{N} \sum\limits_{j=i}^{N} f(i, j)\)
Note that after calculating the value $$f(i, j)$$ for some $$(i, j)$$, the array is restored back to its original form. Therefore, calculating $$f(i, j)$$ for each $$(i, j)$$ pair is independent.
You are given $$T$$ test cases.
Warning: Use FAST I/O Methods.
Input format
- The first line contains a single integer $$T$$ denoting number of test cases.
- For each test case:
- The first line contains a single integer $$N$$ denoting the length of the array.
- The second line contains $$N$$ space-separated integers denoting the integer array $$A$$.
Output format
For each test case, print the required sum in a separate line.
Constraints
$$ 1 \le T \le 1000 \\
1 \le N \le 5 \times 10^5 \\
0 \le A_i < 2^{25} \\
\text{Sum of N over all test cases does not exceed } 10^6 $$