Ecrade has an integer array $a_1, a_2, \ldots, a_n$. It's guaranteed that for each $1 \le i \lt n$, $a_i \neq a_{i+1}$.

Ecrade can perform several operations on the array to make it strictly increasing.

In each operation, he can choose two integers $l$ and $r$ ($1 \le l \le r \le n$) and replace $a_l, a_{l+1}, \ldots, a_r$ with any $r-l+1$ integers $a'_l, a'_{l+1}, \ldots, a'_r$ satisfying the following constraint:

• For each $l \le i \lt r$, the comparison between $a'_i$ and $a'_{i+1}$ is the same as that between $a_i$ and $a_{i+1}$, i.e., if $a_i \lt a_{i + 1}$, then $a'_i \lt a'_{i + 1}$; otherwise, if $a_i \gt a_{i + 1}$, then $a'_i \gt a'_{i + 1}$; otherwise, if $a_i = a_{i + 1}$, then $a'_i = a'_{i + 1}$.

Ecrade wants to know the minimum number of operations to make the array strictly increasing. However, it seems a little difficult, so please help him!

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

It is guaranteed that for each $1 \le i \lt n$, $a_i \neq a_{i+1}$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer representing the minimum number of operations to make the array strictly increasing.

Note

In the first test case, a possible way to obtain the minimum number of operations:

• In the first operation, choose $l = 2, r = 2$ and $a'_2 = 4$, then $a=[3, 4, 1]$;
• In the second operation, choose $l = 1, r = 2$ and $a'_1 = -1, a'_2 = 0$, then $a=[-1, 0, 1]$.

In the second test case, a possible way to obtain the minimum number of operations:

• In the first operation, choose $l = 2, r = 3$ and $a'_2 = 4, a'_3 = 5$, then $a = [3, 4, 5]$.

In the third test case, a possible way to obtain the minimum number of operations:

• In the first operation, choose $l = 2, r = 3$ and $a'_2 = -1, a'_3 = 1$, then $a = [-2, -1, 1, 2]$.