Problem Statement

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$.

You want to satisfy $P_i=i$ for all $i=1,2,\dots,N$ by performing the following operation zero or more times:

• Choose an integer $k$ such that $1 \leq k \leq N$. If $k \geq 2$, sort the $1$-st through $(k-1)$-th terms of $P$ in ascending order. Then, if $k \leq N-1$, sort the $(k+1)$-th through $N$-th terms of $P$ in ascending order.

It can be proved that under the constraints of this problem, it is possible to satisfy $P_i=i$ for all $i=1,2,\dots,N$ with a finite number of operations for any $P$. Find the minimum number of operations required.

You have $T$ test cases to solve.

Constraints

• $1 \leq T \leq 10^5$
• $3 \leq N \leq 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• All input values are integers.
• The sum of $N$ across the test cases in a single input is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
P_1 P_2 \dots P_N

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.