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 $$
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
Login to unlock the editorial
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