CF2261G 1 2 3 and XOR, Where Did Everybody Go?

You are given a sequence $ a $ consisting of $ n $ non-negative integers. Given a sequence $ b $ consisting of $ k $ non-negative integers, define a dot increment on $ b $ as the following operation: - Select an index $ i $ ( $ 1 \le i \le k $ ), and add any non-negative integer of choice to $ b_i $ . Then, let $ f(b) $ be the minimum value of $ b_1 \oplus b_2 \oplus \ldots \oplus b_k $ after performing a dot increment on $ b $ exactly once. $ ^{\text{∗}} $ Please find the value of the following sum. $$$ \sum_{1 \le l \le r \le n}f([a_l,a_{l+1},\ldots,a_r]) $$$ $ ^{\text{∗}} $ Here, $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 4\cdot 10^5 $ ). The second line of each test case contains integers $ a_1,a_2,\ldots,a_n $ ( $ 0 \le a_i \lt 2^{25} $ ). It is guaranteed that the sum of $ n $ does not exceed $ 4\cdot 10^5 $ over all test cases.

For each test case, output the answer to the problem on a separate line.

In the first test case, for example, consider $ f([5,4,6,7,5]) $ By incrementing $ b_2=4 $ by $ 1 $ , $ b $ becomes $ [5,5,6,7,5] $ , and $ 5 \oplus 5 \oplus 6 \oplus 7 \oplus 5 = 4 $ . It can be shown that $ b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5 $ cannot be smaller than $ 4 $ after one dot increment. The sum of minimum values over all subarrays can be shown to be $ 43 $ .