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]$$$.

Balancing

Examples