Yousef has an array $$$a$$$ consisting of $$$n$$$ positive integers.

He defines a reduction operation on any array $$$c$$$ of length $$$|c| \ge 3$$$:

Choose an index $$$i$$$ ($$$1 \lt i \lt |c|$$$) such that $$$c_{i-1} + c_{i+1} \gt c_i$$$.
Replace the triplet $$$\{c_{i-1}, c_i, c_{i+1}\}$$$ with a single integer $$$x = c_{i-1} - c_i + c_{i+1}$$$.

The new integer $$$x$$$ occupies the position previously held by the triplet, and the length of the array decreases by $$$2$$$.

An array is considered good if it can be reduced to a single element by performing the operation above zero or more times. Note that an array of length $$$1$$$ is always good.

Yousef wants you to count the number of pairs $$$(l, r)$$$ ($$$1 \le l \le r \le n$$$) such that the subarray $$$a[l, r]$$$ is good.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array.

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

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

Output

For each test case, output a single integer — the number of good subarrays.

Note

In the first example, $$$a = [10, 20, 10]$$$. Subarrays $$$[10]$$$, $$$[20]$$$, and $$$[10]$$$ are all good ($$$3$$$ total). The subarray $$$[10, 20, 10]$$$ is not good. To reduce it, we must pick $$$i=2$$$. The condition $$$a_1 + a_3 \gt a_2$$$ becomes $$$10 + 10 \gt 20$$$, which is $$$20 \gt 20$$$ (false).

In the second example, $$$a = [1, 1, 1, 1, 1]$$$:

All $$$5$$$ subarrays of length $$$1$$$ are good.
All $$$4$$$ subarrays of length $$$2$$$ are not good.
All $$$3$$$ subarrays of length $$$3$$$ (which are $$$[1, 1, 1]$$$) are good because $$$1 + 1 \gt 1$$$.
All $$$2$$$ subarrays of length $$$4$$$ are not good.
The subarray of length $$$5$$$ is good: $$$[1, 1, 1, 1, 1] \xrightarrow{i=2} [1, 1, 1] \xrightarrow{i=2} [1]$$$.
Total good subarrays $$$= 5 + 3 + 1 = 9$$$.

Drowning

Examples