#include<iostream>
#include<algorithm>
#include<string.h>
#include<utility>
#include<vector>
#include<queue>
#include<cmath>
#include<math.h>
#include<stack>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define LL long long
#define ii pair<int,int>
//#define maxn 2400000
#define SZ(x) x.size()
#define INF (1<<29)
#define pb push_back
#define mp make_pair
#define maxb 1010   
#define sc(x) scanf("%d",&x)
#define mes(x) memset(x.0.sizeof(x))
#define mod 1000000007
#define maxn 600010
#define N 510
#define Q 500010
template<class T> bool chkmax(T& a,const T& b){return a<b?a=b,1:0;}
int read()  
{  
     int num=0; char ch=getchar();
     while(ch<'0'||ch>'9') ch=getchar(); //过滤前面非数字字符
     while(ch>='0'&&ch<='9') {num*=10;num+=ch-'0';ch=getchar();}    
     return num;  
}
LL read1()  
{  
     LL num=0; char ch=getchar();
     while(ch<'0'||ch>'9') ch=getchar(); //过滤前面非数字字符
     while(ch>='0'&&ch<='9') {num*=10;num+=ch-'0';ch=getchar();}    
     return num;  
}

int T,n,b;
int cnt;
int a[200010];
string x;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",&a[i]);
        LL ans=0;
        ans+=n+(n-1);
        FOR(i,3,n) {
            if(a[i-2]<a[i-1]&&a[i-1]>a[i]) ans++;
            else if(a[i-2]>a[i-1]&&a[i-1]<a[i]) ans++;
        }
        FOR(i,4,n) {
            if(a[i-3]<a[i-2]&&a[i-2]>a[i-1]&&a[i-1]<a[i]&&a[i-3]>a[i-1]&&a[i-2]>a[i]) ans++;
            else if(a[i-3]>a[i-2]&&a[i-2]<a[i-1]&&a[i-1]>a[i]&&a[i-3]<a[i-1]&&a[i-2]<a[i]) ans++;
            //else if(a[i-3]>a[i-2]&&a[i-2]==a[i-1]&&a[i-1]<a[i]) ans++;
            //else if(a[i-3]<a[i-2]&&a[i-2]==a[i-1]&&a[i-1]>a[i]) ans++; 
        }
        cout<<ans<<endl;
    }
    return 0;
} 
### Prompt

Generate 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<iostream>
#include<algorithm>
#include<string.h>
#include<utility>
#include<vector>
#include<queue>
#include<cmath>
#include<math.h>
#include<stack>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define LL long long
#define ii pair<int,int>
//#define maxn 2400000
#define SZ(x) x.size()
#define INF (1<<29)
#define pb push_back
#define mp make_pair
#define maxb 1010   
#define sc(x) scanf("%d",&x)
#define mes(x) memset(x.0.sizeof(x))
#define mod 1000000007
#define maxn 600010
#define N 510
#define Q 500010
template<class T> bool chkmax(T& a,const T& b){return a<b?a=b,1:0;}
int read()  
{  
     int num=0; char ch=getchar();
     while(ch<'0'||ch>'9') ch=getchar(); //过滤前面非数字字符
     while(ch>='0'&&ch<='9') {num*=10;num+=ch-'0';ch=getchar();}    
     return num;  
}
LL read1()  
{  
     LL num=0; char ch=getchar();
     while(ch<'0'||ch>'9') ch=getchar(); //过滤前面非数字字符
     while(ch>='0'&&ch<='9') {num*=10;num+=ch-'0';ch=getchar();}    
     return num;  
}

int T,n,b;
int cnt;
int a[200010];
string x;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",&a[i]);
        LL ans=0;
        ans+=n+(n-1);
        FOR(i,3,n) {
            if(a[i-2]<a[i-1]&&a[i-1]>a[i]) ans++;
            else if(a[i-2]>a[i-1]&&a[i-1]<a[i]) ans++;
        }
        FOR(i,4,n) {
            if(a[i-3]<a[i-2]&&a[i-2]>a[i-1]&&a[i-1]<a[i]&&a[i-3]>a[i-1]&&a[i-2]>a[i]) ans++;
            else if(a[i-3]>a[i-2]&&a[i-2]<a[i-1]&&a[i-1]>a[i]&&a[i-3]<a[i-1]&&a[i-2]<a[i]) ans++;
            //else if(a[i-3]>a[i-2]&&a[i-2]==a[i-1]&&a[i-1]<a[i]) ans++;
            //else if(a[i-3]<a[i-2]&&a[i-2]==a[i-1]&&a[i-1]>a[i]) ans++; 
        }
        cout<<ans<<endl;
    }
    return 0;
} 
```