First One

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.

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)$.

For each test case, output the value.

1
2
1 1

12

zimpha@zju

2015 Multi-University Training Contest 6