First One

Problem Description

soda has an integer array $a_1, a_2, \dots, a_n$. Let $S(i,j)$ be the sum of $a_i, a_{i+1}, \dots, a_j$. Now soda wants to know the value below: $$\sum_{i=1}^{n} \sum_{j=i}^{n} (\lfloor \log_2 S(i,j) \rfloor + 1) \times (i + j)$$ Note: In this problem, you can consider $\log_2 0$ as 0.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ $(1 \le n \le 10^5)$, the number of integers in the array. The next line contains $n$ integers $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^5)$.

Output

For each test case, output the value.

Sample Input

1
2
1 1

Sample Output

12

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6