/**
 * Author: Fau
 * Time: 2021-07-15 14:32
**/

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(a) cout << #a << " = " << a << endl
using namespace std;
typedef long long ll;
const int N = 2E5 + 10;
int a[N];

int fact(int x, int y) {
	if (a[x] == a[y]) return 0;
	if (a[x] < a[y]) return -1;
	return 1;
}
bool judge(int l, int r) {
	if (r - l + 1 <= 2) return 1;
	if (r - l + 1 >= 5) return 0;

	if (r - l + 1 == 3) {
		int x = fact(l, l + 1);
		int y = fact(l + 1, r);
		if (x == y or !x or !y) return 0;
		return 1;
	}

	if (a[l + 1] >= a[l]) {
		if (a[l + 2] >= a[l]) return 0;
		if (a[r] <= a[l + 2] or a[r] >= a[l + 1]) return 0;
		return 1;
	}
	else {
		if (a[l + 2] <= a[l]) return 0;
		if (a[r] >= a[l + 2] or a[r] <= a[l + 1]) return 0;
		return 1;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("/Users/Fau/Documents/Fau/project/Clion Program/TEXT/in.txt", "r", stdin);
	freopen("/Users/Fau/Documents/Fau/project/Clion Program/TEXT/out.txt", "w", stdout);
#endif
//------------------------------------------------------------CODE BEGIN------------------------------------------------------------

	int t; cin >> t;
	while (t--) {
		int n; scanf("%d", &n);
		rep(i, n) scanf("%d", &a[i]);

		int res = 0;
		for (int l = 1; l <= n; ++l) {
			for (int r = l; r <= n; ++r) {
				if (judge(l, r)) {
					//cout << l << ' ' << r << endl;
					res++;
				}
				else break;
			}
		}

		printf("%d\n", res);
	}

//-------------------------------------------------------------CODE END-------------------------------------------------------------
#ifndef ONLINE_JUDGE
	fclose(stdout);
	system("/Users/Fau/Documents/Fau/project/Clion\\ Program/compare_Fau");
#endif
	return 0;
}
### Prompt

Please create a solution in Cpp 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
/**
 * Author: Fau
 * Time: 2021-07-15 14:32
**/

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(a) cout << #a << " = " << a << endl
using namespace std;
typedef long long ll;
const int N = 2E5 + 10;
int a[N];

int fact(int x, int y) {
	if (a[x] == a[y]) return 0;
	if (a[x] < a[y]) return -1;
	return 1;
}
bool judge(int l, int r) {
	if (r - l + 1 <= 2) return 1;
	if (r - l + 1 >= 5) return 0;

	if (r - l + 1 == 3) {
		int x = fact(l, l + 1);
		int y = fact(l + 1, r);
		if (x == y or !x or !y) return 0;
		return 1;
	}

	if (a[l + 1] >= a[l]) {
		if (a[l + 2] >= a[l]) return 0;
		if (a[r] <= a[l + 2] or a[r] >= a[l + 1]) return 0;
		return 1;
	}
	else {
		if (a[l + 2] <= a[l]) return 0;
		if (a[r] >= a[l + 2] or a[r] <= a[l + 1]) return 0;
		return 1;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("/Users/Fau/Documents/Fau/project/Clion Program/TEXT/in.txt", "r", stdin);
	freopen("/Users/Fau/Documents/Fau/project/Clion Program/TEXT/out.txt", "w", stdout);
#endif
//------------------------------------------------------------CODE BEGIN------------------------------------------------------------

	int t; cin >> t;
	while (t--) {
		int n; scanf("%d", &n);
		rep(i, n) scanf("%d", &a[i]);

		int res = 0;
		for (int l = 1; l <= n; ++l) {
			for (int r = l; r <= n; ++r) {
				if (judge(l, r)) {
					//cout << l << ' ' << r << endl;
					res++;
				}
				else break;
			}
		}

		printf("%d\n", res);
	}

//-------------------------------------------------------------CODE END-------------------------------------------------------------
#ifndef ONLINE_JUDGE
	fclose(stdout);
	system("/Users/Fau/Documents/Fau/project/Clion\\ Program/compare_Fau");
#endif
	return 0;
}
```