A permutation$^{\text{∗}}$ $p$ of length $n$ is written clockwise on a circular dial.

Choose a starting position $s$ ($1\le s\le n$) and read one full circle clockwise from $p_s$, wrapping around after $p_n$. The resulting sequence is

$$ q=[p_s,p_{s+1},\ldots,p_n,p_1,\ldots,p_{s-1}], $$

which also has a length of $n$.

For any non-empty prefix of this sequence $[q_1, q_2, \ldots, q_k]$ ($k\ge 1$), let $S$ be the corresponding set of values, that is, $S=\{q_1, q_2,\ldots, q_k\}$. Split $S$ into maximal segments of consecutive integers, and we call these segments the blocks of $S$.

For example, $S=\{1,2,5,7,8,9\}$ has $3$ blocks: $\{1,2\}$, $\{5\}$, and $\{7,8,9\}$.

A starting position $s$ is called good if and only if, for every non-empty prefix of $q$, the corresponding set $S$ has at most $2$ blocks.

Find the number of good starting positions.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

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 one integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of $p$.

The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.

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

Output

For each test case, print one integer — the number of good starting positions.

Note

In the first test case, there is only one starting position. Every non-empty prefix contains the single value $1$, so it has one block. Thus, this position is good.

In the second test case, after reading the first $3$ numbers from position $1$, the set is $\{1,3,5\}$ and has $3$ blocks. Thus, position $1$ is not good. Each of the other $4$ positions is good.