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
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 $$
Consider the first test case, $$N = 3$$, $$ A = [3, 4, 1]$$. We want to evaluate $$f(1, 1) + f(1, 2) + f(2, 2) + f(2, 3) + f(3, 3)$$. Calculations are shown below:
Consider the second test case, $$N = 2$$, $$ A = [4, 2]$$. We want to evaluate $$f(1, 1) + f(2, 2) $$. Calculations are shown below: