You are given an array \(A\) of size \(N\). Your task is to find the number of subarrays within the given array such that the Bitwise XOR of all elements in the subarray has an odd number of set bits (i.e., 1s).
The subarray of \(A\) is a contiguous part of the array \(A\), i. e. the array \(A_i, A_{i + 1}, ...., A_j\) for some \(1 \leq i \leq j \leq N\).
Input format
Output format
For each test case, print the number of subarrays within the given array such that the Bitwise XOR of all elements in the subarray has an odd number of set bits (i.e., 1s) in a new line.
Constraints
\(1 \leq T \leq 10^5 \\ 1 \leq N \leq 10^6 \\ 1≤A[i]≤10^9\ ∀\ i∈[1,N] \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6\)
For test case \(1\):
In the given array there are the following 4 subarrays with their XOR having odd number of set bits:
Thus, the answer is 4.