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 $$
2 3 3 4 1 2 4 2
5 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:
- $$f(1, 1)$$ : Replace $$A_1$$ with $$(2^{25} - 1)$$, we get $$A = [33554431, 4, 1]$$, Bitwise AND of elements is 0.
- $$f(1, 2)$$ : Replace $$A_1, A_2$$ with $$(2^{25} - 1)$$, we get $$A = [33554431, 33554431, 1]$$, Bitwise AND of elements is 1.
- $$f(2, 2)$$ : Replace $$A_2$$ with $$(2^{25} - 1)$$, we get $$A = [3, 33554431, 1]$$, Bitwise AND of elements is 1.
- $$f(2, 3)$$ : Replace $$A_2, A_3$$ with $$(2^{25} - 1)$$, we get $$A = [3, 33554431, 33554431]$$, Bitwise AND of elements is 3.
- $$f(3, 3)$$ : Replace $$A_3$$ with $$(2^{25} - 1)$$, we get $$A = [3, 4, 33554431]$$, Bitwise AND of elements is 0.
- The sum is $$0 + 1 + 1 + 3 + 0 = 5$$.
Consider the second test case, $$N = 2$$, $$ A = [4, 2]$$. We want to evaluate $$f(1, 1) + f(2, 2) $$. Calculations are shown below:
- $$f(1, 1)$$ : Replace $$A_1$$ with $$(2^{25} - 1)$$, we get $$A = [33554431, 2]$$, Bitwise AND of elements is 2.
- $$f(2, 2)$$ : Replace $$A_2$$ with $$(2^{25} - 1)$$, we get $$A = [4, 33554431]$$, Bitwise AND of elements is 4.
- The sum is $$2 + 4 = 6$$.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor