#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define MAX(a, b) ((a > b)? a : b)
#define MIN(a, b) ((a < b)? a : b)
#define ll long long int

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t-- > 0)
    {
        ll n;
        cin >> n;

        vector<ll> arr(n);
        for (ll i = 0; i < n; ++i) {
            cin >> arr[i];
        }

        ll count = 2 * n - 1;

        // Checking for len = 4
        //      6 9 1 9 6
        // 6 9 1 9      9 1 9 6
        // 4C3 = 4

        if (n == 3) {
            ll d1 = abs(arr[2] - arr[0]) + 2;
            ll d2 = abs(arr[1] - arr[0]) + 1;
            ll d3 = abs(arr[2] - arr[1]) + 1;
            if (d1 != d2 + d3) count++;
        }

        for (ll i = 0; i < n - 3; ++i) {
            // 012
            bool flag1 = false;
            // cout << arr[i] << " " <<  arr[i + 1] << " " << arr[i + 2] << " " << arr[i + 3] << endl;
            ll d1 = abs(arr[i + 2] - arr[i]) + 2;
            ll d2 = abs(arr[i + 1] - arr[i]) + 1;
            ll d3 = abs(arr[i + 2] - arr[i + 1]) + 1;
            if (d1 != d2 + d3) {
                flag1 = true;
                // cout << arr[i] << " " << arr[i + 1] << " " << arr[i + 2] << endl;
                count++;
            }

            // 123
            bool flag2 = false;
            d1 = abs(arr[i + 3] - arr[i + 1]) + 2;
            d2 = abs(arr[i + 2] - arr[i + 1]) + 1;
            d3 = abs(arr[i + 3] - arr[i + 2]) + 1;
            if (d1 != d2 + d3) {
                flag2 = true;
                // cout << arr[i + 1] << " " << arr[i + 2] << " " << arr[i + 3] << endl;
                // count++;
            }

            // 013
            bool flag3 = false;
            d1 = abs(arr[i + 3] - arr[i]) + 3;
            d2 = abs(arr[i + 1] - arr[i]) + 1;
            d3 = abs(arr[i + 3] - arr[i + 1]) + 2;
            if (d1 != d2 + d3) {
                flag3 = true;
                // count++;
            }

            // 023
            bool flag4 = false;
            d1 = abs(arr[i + 3] - arr[i]) + 3;
            d2 = abs(arr[i + 2] - arr[i]) + 2;
            d3 = abs(arr[i + 3] - arr[i + 2]) + 1;
            if (d1 != d2 + d3) {
                flag4 = true;
                // count++;
            }

            if (flag1 && flag2 && flag3 && flag4)
                count++;
        }

        if (n > 3) {
            ll d1 = abs(arr[n - 1] - arr[n - 3]) + 2;
            ll d2 = abs(arr[n - 1] - arr[n - 2]) + 1;
            ll d3 = abs(arr[n - 2] - arr[n - 3]) + 1;
            if (d1 != d2 + d3) count++;
        }
        cout << count << endl;
    }
}

### Prompt

Develop a solution in CPP to the problem described below:

Suppose you have two points p = (x_p, y_p) and q = (x_q, y_q). Let's denote the Manhattan distance between them as d(p, q) = |x_p - x_q| + |y_p - y_q|.

Let's say that three points p, q, r form a bad triple if d(p, r) = d(p, q) + d(q, r).

Let's say that an array b_1, b_2, ..., b_m is good if it is impossible to choose three distinct indices i, j, k such that the points (b_i, i), (b_j, j) and (b_k, k) form a bad triple.

You are given an array a_1, a_2, ..., a_n. Calculate the number of good subarrays of a. A subarray of the array a is the array a_l, a_{l + 1}, ..., a_r for some 1 ≤ l ≤ r ≤ n.

Note that, according to the definition, subarrays of length 1 and 2 are good.

Input

The first line contains one integer t (1 ≤ t ≤ 5000) — the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of array a.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

It's guaranteed that the sum of n doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print the number of good subarrays of array a.

Example

Input


3
4
2 4 1 3
5
6 9 1 9 6
2
13 37


Output


10
12
3

Note

In the first test case, it can be proven that any subarray of a is good. For example, subarray [a_2, a_3, a_4] is good since it contains only three elements and: 

  * d((a_2, 2), (a_4, 4)) = |4 - 3| + |2 - 4| = 3 < d((a_2, 2), (a_3, 3)) + d((a_3, 3), (a_4, 4)) = 3 + 1 + 2 + 1 = 7; 
  * d((a_2, 2), (a_3, 3)) < d((a_2, 2), (a_4, 4)) + d((a_4, 4), (a_3, 3)); 
  * d((a_3, 3), (a_4, 4)) < d((a_3, 3), (a_2, 2)) + d((a_2, 2), (a_4, 4)); 



In the second test case, for example, subarray [a_1, a_2, a_3, a_4] is not good, since it contains a bad triple (a_1, 1), (a_2, 2), (a_4, 4): 

  * d((a_1, 1), (a_4, 4)) = |6 - 9| + |1 - 4| = 6; 
  * d((a_1, 1), (a_2, 2)) = |6 - 9| + |1 - 2| = 4; 
  * d((a_2, 2), (a_4, 4)) = |9 - 9| + |2 - 4| = 2; 



So, d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 4)).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define MAX(a, b) ((a > b)? a : b)
#define MIN(a, b) ((a < b)? a : b)
#define ll long long int

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t-- > 0)
    {
        ll n;
        cin >> n;

        vector<ll> arr(n);
        for (ll i = 0; i < n; ++i) {
            cin >> arr[i];
        }

        ll count = 2 * n - 1;

        // Checking for len = 4
        //      6 9 1 9 6
        // 6 9 1 9      9 1 9 6
        // 4C3 = 4

        if (n == 3) {
            ll d1 = abs(arr[2] - arr[0]) + 2;
            ll d2 = abs(arr[1] - arr[0]) + 1;
            ll d3 = abs(arr[2] - arr[1]) + 1;
            if (d1 != d2 + d3) count++;
        }

        for (ll i = 0; i < n - 3; ++i) {
            // 012
            bool flag1 = false;
            // cout << arr[i] << " " <<  arr[i + 1] << " " << arr[i + 2] << " " << arr[i + 3] << endl;
            ll d1 = abs(arr[i + 2] - arr[i]) + 2;
            ll d2 = abs(arr[i + 1] - arr[i]) + 1;
            ll d3 = abs(arr[i + 2] - arr[i + 1]) + 1;
            if (d1 != d2 + d3) {
                flag1 = true;
                // cout << arr[i] << " " << arr[i + 1] << " " << arr[i + 2] << endl;
                count++;
            }

            // 123
            bool flag2 = false;
            d1 = abs(arr[i + 3] - arr[i + 1]) + 2;
            d2 = abs(arr[i + 2] - arr[i + 1]) + 1;
            d3 = abs(arr[i + 3] - arr[i + 2]) + 1;
            if (d1 != d2 + d3) {
                flag2 = true;
                // cout << arr[i + 1] << " " << arr[i + 2] << " " << arr[i + 3] << endl;
                // count++;
            }

            // 013
            bool flag3 = false;
            d1 = abs(arr[i + 3] - arr[i]) + 3;
            d2 = abs(arr[i + 1] - arr[i]) + 1;
            d3 = abs(arr[i + 3] - arr[i + 1]) + 2;
            if (d1 != d2 + d3) {
                flag3 = true;
                // count++;
            }

            // 023
            bool flag4 = false;
            d1 = abs(arr[i + 3] - arr[i]) + 3;
            d2 = abs(arr[i + 2] - arr[i]) + 2;
            d3 = abs(arr[i + 3] - arr[i + 2]) + 1;
            if (d1 != d2 + d3) {
                flag4 = true;
                // count++;
            }

            if (flag1 && flag2 && flag3 && flag4)
                count++;
        }

        if (n > 3) {
            ll d1 = abs(arr[n - 1] - arr[n - 3]) + 2;
            ll d2 = abs(arr[n - 1] - arr[n - 2]) + 1;
            ll d3 = abs(arr[n - 2] - arr[n - 3]) + 1;
            if (d1 != d2 + d3) count++;
        }
        cout << count << endl;
    }
}

```