70007 - CF2241G

G. Summmon

time limit per test: 4 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

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

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([al,a{l+1},\dots,a_r])$.

Example

Input

5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6

Output

4
3
39
72
111

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.