#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
const int mod = 998244353;
const ll INF = -9999999999999;
const int maxn = 1000006;
const int maxm = 1000006;
const int ox3f = 1061109567;
const int fox3f = -2139062144;
const ll ox3fll = 4557430888798830399;
int n, m, t;
int a[200005];
bool pd(int i, int j, int k)
{
    if(a[i]<a[j] && a[j]>a[k])return true;
    if(a[i]>a[j] && a[j]<a[k]) return true;
    return false;
}
bool pd4(int i,int j,int k,int l)
{
    if(pd(i,j,k)&&pd(i,j,l) && pd(i,k,l) && pd(j,k,l)) return true;
    return false;
}
void solve() {
    cin >> t;
    while(t--)
    {
        cin >> n;
        ll cnt = 0;
        for(int i=1;i<=n;i++)
            cin >> a[i];
        for(int i=1;i<=n;i++)
        {
            if(i+2<=n)
                if(pd(i,i+1,i+2)) cnt++;
            if(i+3<=n)
                if(pd4(i,i+1,i+2,i+3)) cnt++;
        }
        cnt += (n+n-1);
        cout << cnt << endl;
    }


}

signed main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
#ifdef FJH_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#else
    solve();
#endif
    return 0;
}


### Prompt

Please provide a cpp coded solution 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;
typedef long long ll;
const int mod = 998244353;
const ll INF = -9999999999999;
const int maxn = 1000006;
const int maxm = 1000006;
const int ox3f = 1061109567;
const int fox3f = -2139062144;
const ll ox3fll = 4557430888798830399;
int n, m, t;
int a[200005];
bool pd(int i, int j, int k)
{
    if(a[i]<a[j] && a[j]>a[k])return true;
    if(a[i]>a[j] && a[j]<a[k]) return true;
    return false;
}
bool pd4(int i,int j,int k,int l)
{
    if(pd(i,j,k)&&pd(i,j,l) && pd(i,k,l) && pd(j,k,l)) return true;
    return false;
}
void solve() {
    cin >> t;
    while(t--)
    {
        cin >> n;
        ll cnt = 0;
        for(int i=1;i<=n;i++)
            cin >> a[i];
        for(int i=1;i<=n;i++)
        {
            if(i+2<=n)
                if(pd(i,i+1,i+2)) cnt++;
            if(i+3<=n)
                if(pd4(i,i+1,i+2,i+3)) cnt++;
        }
        cnt += (n+n-1);
        cout << cnt << endl;
    }


}

signed main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
#ifdef FJH_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#else
    solve();
#endif
    return 0;
}


```