The grader reads the test in the following format:

The first line contains the number $t$ ($1 \le t \le 30\,000$)~--- the number of input data sets.

The first line of each input data set contains an \textbf{odd} number $n$ ($1 \le n \le 30\,000$)~--- the length of the permutation.

The second line contains $n$ distinct numbers $p_1, \ldots, p_n$ ($1 \le p_i \le n$)~--- the chosen permutation.