#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}
ll ceil(ll a,ll b){
    ll ans=a/b;
    if(a%b)ans++;
    return ans;
}
ld log (ld a,ld b){return log(b)/log(a);}
ll power(ll base, ll exp,ll M=1e18){//(base^exp)%M
    ll ans=1;
    while(exp){
        if(exp%2==1)ans=((ans%M)*(base%M))%M;
        base=((base%M)*(base%M))%M;
        exp/=2;
    }
    return ans;
}

string to_base(int n,int new_base){
    string s;
    int nn=n;
    while(nn){
        s+=to_string(nn%new_base);
        nn/=new_base;
    }
    reverse(all(s));
    return s;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll x= (a/gcd(a,b));
    return b*x;
}
vl generate_array(ll n,ll mn=1,ll mx=1e18+1){
    if(mx==1e18+1)
        mx=n;
    vl ans(n);
    for(int i=0; i<n;i++)
        ans[i]=(mn+rand()%(mx-mn+1));
    return ans;
}
string substr(string s,int l,int r){
    string ans;
    for(int i=l; i<=r; i++)
        ans+=s[i];
    return ans;
}


void solve();
int main(){
    GLHF;
    int t=1;
    cin >> t;
    while(t--)
        solve();
}
bool ok(vpl a){
    int n=a.size();
    for(int i=0; i<n; i++)
        for(int j=0; j<n ;j++)
            for(int k=0; k<n ;k++)
                if(i!=j && i!=k && j!=k)
                    if(abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second)==abs(a[i].second-a[k].second) + abs(a[i].first-a[k].first) + abs(a[j].second-a[k].second) + abs(a[j].first-a[k].first))
                        return 0;
    return 1;
}
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    read(a);

    ll ans=0;
    for(int i=0; i<n; i++){
        vpl cur={{a[i], i + 1}};
        ans++;
        for(int j=i+1; j<n; j++){
            cur.pb({a[j],j+1});
            if(!ok(cur))break;
            ans++;
        }
    }
    out(ans)
}
### Prompt

Please formulate 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>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}
ll ceil(ll a,ll b){
    ll ans=a/b;
    if(a%b)ans++;
    return ans;
}
ld log (ld a,ld b){return log(b)/log(a);}
ll power(ll base, ll exp,ll M=1e18){//(base^exp)%M
    ll ans=1;
    while(exp){
        if(exp%2==1)ans=((ans%M)*(base%M))%M;
        base=((base%M)*(base%M))%M;
        exp/=2;
    }
    return ans;
}

string to_base(int n,int new_base){
    string s;
    int nn=n;
    while(nn){
        s+=to_string(nn%new_base);
        nn/=new_base;
    }
    reverse(all(s));
    return s;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll x= (a/gcd(a,b));
    return b*x;
}
vl generate_array(ll n,ll mn=1,ll mx=1e18+1){
    if(mx==1e18+1)
        mx=n;
    vl ans(n);
    for(int i=0; i<n;i++)
        ans[i]=(mn+rand()%(mx-mn+1));
    return ans;
}
string substr(string s,int l,int r){
    string ans;
    for(int i=l; i<=r; i++)
        ans+=s[i];
    return ans;
}


void solve();
int main(){
    GLHF;
    int t=1;
    cin >> t;
    while(t--)
        solve();
}
bool ok(vpl a){
    int n=a.size();
    for(int i=0; i<n; i++)
        for(int j=0; j<n ;j++)
            for(int k=0; k<n ;k++)
                if(i!=j && i!=k && j!=k)
                    if(abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second)==abs(a[i].second-a[k].second) + abs(a[i].first-a[k].first) + abs(a[j].second-a[k].second) + abs(a[j].first-a[k].first))
                        return 0;
    return 1;
}
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    read(a);

    ll ans=0;
    for(int i=0; i<n; i++){
        vpl cur={{a[i], i + 1}};
        ans++;
        for(int j=i+1; j<n; j++){
            cur.pb({a[j],j+1});
            if(!ok(cur))break;
            ans++;
        }
    }
    out(ans)
}
```