Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128.

For any array $$$b$$$ of length $$$m$$$, define $$$f(b)$$$ as the minimum possible value of $$$\max(b) - \min(b)$$$ that can be achieved by performing the following operation any number of times:

Choose any index $$$1 \le i \lt m$$$, and do exactly one of the following:
1. Set $$$b_{i+1} := b_{i+1} + b_i$$$,
2. Set $$$b_{i+1} := b_{i+1} - b_i$$$.

You are given an array $$$a$$$ of length $$$n$$$. Your task is to compute the sum of $$$f$$$ over all the subarrays$$$^{\text{∗}}$$$ of $$$a$$$. More formally, determine the value of

$$$$$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]).$$$$$$

$$$^{\text{∗}}$$$An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, print a single integer — the value of $$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r])$$$.

Note

For the first test case, let us look at all subarrays.

For the single-element subarrays $$$[6]$$$, $$$[4]$$$, and $$$[8]$$$, no operation can change anything, so each of them contributes $$$0$$$.
For $$$[6,4]$$$, the first element is fixed as $$$6$$$. The second element can only be changed to $$$4+6=10$$$ or $$$4-6=-2$$$, so the gap would become $$$4$$$ or $$$8$$$. Hence, doing no operation is best, and the contribution is $$$2$$$.
For $$$[4,8]$$$, we choose $$$i=1$$$ and apply $$$b_{2}:=b_{2}-b_{1}$$$. Then the subarray becomes $$$[4,4]$$$, so its contribution is $$$0$$$.
For $$$[6,4,8]$$$, we keep the first two elements as they are and choose $$$i=2$$$. Then we apply $$$b_{3}:=b_{3}-b_{2}$$$, so $$$8$$$ becomes $$$4$$$. The array becomes $$$[6,4,4]$$$, and therefore $$$\max(b)-\min(b)=6-4=2$$$. It can be shown that this is the optimal value.

Therefore, the answer for the first test case is $$$0+0+0+2+0+2=4$$$.

For the second test case, every subarray of length $$$1$$$ contributes $$$0$$$. Among the remaining subarrays, only $$$[2,3]$$$, $$$[3,4]$$$, and $$$[2,3,4]$$$ have a non-zero contribution, each contributing $$$1$$$. Therefore, the answer is $$$1+1+1=3$$$.

Idx	Name	Rating
A	Divide and Conquer	800
B	Good times Good times	1100
C	RemovevomeR	1000
D	An Alternative Way	1100
E	Fair and Square	1600
F	A Bit Odd	1700
G	Summmon	2400

Codeforces Round (Div. 3)