Una permutazione di dimensione $n$ è una sequenza di $n$ interi $a_1,a_2,\ldots,a_n$ in cui tutti i valori da $1$ a $n$ compaiono esattamente una volta.

La sequenza $b_1,b_2,\ldots,b_l$ è una sottosequenza della sequenza $a_1,a_2,\ldots,a_n$ se $b$ può essere ottenuta da $a$ eliminando alcuni elementi (cioè $l\le n$ ed esistono $i_1<i_2<\cdots<i_l$ tali che $a_{i_t}=b_t$).

• Un elemento $a_i$ di una sequenza è detto record se è strettamente maggiore di tutti gli elementi precedenti (cioè $a_j<a_i$ per ogni $1\le j<i$).
• Un elemento $a_i$ di una sequenza è detto antirecord se è strettamente minore di tutti gli elementi precedenti (cioè $a_j>a_i$ per ogni $1\le j<i$).

È data una permutazione $p_1,p_2,\ldots,p_n$ di dimensione $n$. Occorre dividerla in due sottosequenze non vuote $q$ e $r$. In altre parole, ogni elemento di $p$ deve appartenere esattamente a una delle sottosequenze. Si deve massimizzare la somma del numero di record in $q$ e del numero di antirecord in $r$.

Input

Ogni test contiene più casi di test. La prima riga contiene un unico intero $t$ ($1\le t\le 100\,000$), il numero di casi di test. Le successive $2t$ righe contengono le descrizioni dei casi di test.

La prima riga della descrizione di ciascun caso di test contiene un intero $n$, la dimensione della permutazione ($2\le n\le 200\,000$).

La seconda riga della descrizione di ciascun caso di test contiene $n$ interi $p_1,p_2,\ldots,p_n$, la permutazione iniziale. È garantito che ciascun numero da $1$ a $n$ compaia esattamente una volta fra gli elementi di $p$.

La somma di $n$ su tutti i casi di test non supera $200\,000$.

Output

Per ogni caso di test, stampare un intero: la massima somma possibile del numero di record in $q$ e di antirecord in $r$ in una divisione ottimale.

Sottoproblemi

Indichiamo con $N$ la somma dei valori di $n$ su tutti i casi di test di un test.

Esempi

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

Nota

Un modo di dividere $p$ in $q$ e $r$ in modo ottimale nel primo caso di test è il seguente (i record di $q$ e gli antirecord di $r$ sono riquadrati):

• $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r=\boxed{4}$

Un modo di dividere $p$ in $q$ e $r$ in modo ottimale nel secondo caso di test è il seguente:

• $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$