A permutation of size $n$ is a sequence of $n$ integers $a_1, a_2, \dots, a_n$ in which every value from $1$ to $n$ appears exactly once.

A sequence $b_1, b_2, \dots, b_l$ is a subsequence of the sequence $a_1, a_2, \dots, a_n$ if $b$ can be obtained from $a$ by deleting some elements (i.e., $l \le n$ and there exist $i_1 < i_2 < \dots < i_l$ such that $a_{i_t} = b_t$).

• An element $a_i$ of a sequence is called a record if it is strictly greater than all previous elements (i.e., $a_j < a_i$ for all $1 \le j < i$).
• An element $a_i$ of a sequence is called an anti-record if it is strictly less than all previous elements (i.e., $a_j > a_i$ for all $1 \le j < i$).

Given a permutation $p_1, p_2, \dots, p_n$ of size $n$, you need to partition it into two non-empty subsequences $q$ and $r$. In other words, every element of $p$ must belong to exactly one of the subsequences. You are required to maximize the sum of the number of records in $q$ and the number of anti-records in $r$.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 100\,000$) — the number of test cases. The next $2t$ lines contain the descriptions of the test cases.

The first line of each test case description contains a single integer $n$ — the size of the permutation ($2 \le n \le 200\,000$).

The second line of each test case description contains $n$ integers $p_1, p_2, \dots, p_n$ — the initial permutation. It is guaranteed that among the elements of $p$, each number from $1$ to $n$ appears exactly once.

The sum of $n$ over all test cases does not exceed $200\,000$.

Output

For each test case, output a single integer — the maximum possible sum of the number of records in $q$ and anti-records in $r$ in an optimal partition.

Subtasks

Let $N$ be the sum of $n$ over all test cases in a single test.

Examples

Input 1

4
5
4 1 2 3 5
10
3 8 10 4 1 2 7 9 5 6
3
1 2 3
6
4 2 5 1 6 3

Output 1

5
6
3
5

Note

One way to optimally partition $p$ into $q$ and $r$ for the first test case (records in $q$ and anti-records in $r$ are circled):

• $q = 1, 2, 3, 5$
• $r = 4$

One way to optimally partition $p$ into $q$ and $r$ for the second test case:

• $q = 3, 8, 4, 1, 2, 9$
• $r = 10, 7, 5, 6$