#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define debug freopen("1.in", "r", stdin), freopen("1.out", "w", stdout)
#define mem(a,b) memset(a,b,sizeof(a))
#define inv(a,p) fpow(a,p-2,p)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pw(a) (1LL<<a)
#define ls(a) (a<<1LL)
#define rs(a) (a<<1LL|1LL)
#define make make_pair
#define PP push_back
#define x first
#define y second
using namespace std;
 
typedef long long LL;
typedef double DD;
typedef bool BB;
typedef pair<string,LL> PAIR;
 
const LL INF=1e18;
const LL mod=1e9+7;
const LL N=2e5+10;
 
LL n,m,k,T,cnt,ans,sum;
LL arr[N];
LL check(LL x)
{
    if((arr[x-1]>arr[x])&&(arr[x+1]>arr[x])||(arr[x-1]<arr[x])&&(arr[x+1]<arr[x])) return 1;
    else return 0;
}
LL ok(LL x,LL y,LL z)
{
    if((x>z&&x<y)||(x<z&&x>y)) return 1;
    return 0;
}
LL gcd(LL a,LL b){return (b==0)?a:gcd(b,a%b);}
int main(void)
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        for(LL i=1;i<=n;i++) scanf("%lld",&arr[i]);
        ans=n+n-1;
        for(LL i=2;i<=n-1;i++)
        {
            if(!check(i)) continue;
            if(i==n-1)
            {
                ans++;
                continue;
            }
            if(check(i+1))
            {
                if(ok(arr[i-1],arr[i],arr[i+1])&&ok(arr[i+2],arr[i+1],arr[i]))
                {
                    i++;
                    ans+=3;
                } 
                else ans++;
            }
            else ans++;
        }
        cout<<ans<<endl;
    }
    // system("pause");
    return 0;
}
### Prompt

Your task is to create a cpp solution to the following problem:

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>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define debug freopen("1.in", "r", stdin), freopen("1.out", "w", stdout)
#define mem(a,b) memset(a,b,sizeof(a))
#define inv(a,p) fpow(a,p-2,p)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pw(a) (1LL<<a)
#define ls(a) (a<<1LL)
#define rs(a) (a<<1LL|1LL)
#define make make_pair
#define PP push_back
#define x first
#define y second
using namespace std;
 
typedef long long LL;
typedef double DD;
typedef bool BB;
typedef pair<string,LL> PAIR;
 
const LL INF=1e18;
const LL mod=1e9+7;
const LL N=2e5+10;
 
LL n,m,k,T,cnt,ans,sum;
LL arr[N];
LL check(LL x)
{
    if((arr[x-1]>arr[x])&&(arr[x+1]>arr[x])||(arr[x-1]<arr[x])&&(arr[x+1]<arr[x])) return 1;
    else return 0;
}
LL ok(LL x,LL y,LL z)
{
    if((x>z&&x<y)||(x<z&&x>y)) return 1;
    return 0;
}
LL gcd(LL a,LL b){return (b==0)?a:gcd(b,a%b);}
int main(void)
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        for(LL i=1;i<=n;i++) scanf("%lld",&arr[i]);
        ans=n+n-1;
        for(LL i=2;i<=n-1;i++)
        {
            if(!check(i)) continue;
            if(i==n-1)
            {
                ans++;
                continue;
            }
            if(check(i+1))
            {
                if(ok(arr[i-1],arr[i],arr[i+1])&&ok(arr[i+2],arr[i+1],arr[i]))
                {
                    i++;
                    ans+=3;
                } 
                else ans++;
            }
            else ans++;
        }
        cout<<ans<<endl;
    }
    // system("pause");
    return 0;
}
```