Minimum Triple#12307
Sign in

Minimum Triple

1 second
256 megabytes
Medium

You are given a permutation of length (i.e., it contains every integer from to exactly once).

In one operation, you choose three distinct indices i, j, k such that 1 \le i < j < k \le n and apply one of the following cyclic shifts:

(p_i, p_j, p_k) \leftarrow (p_j, p_k, p_i) \quad \text{or} \quad (p_i, p_j, p_k) \leftarrow (p_k, p_i, p_j).

That is, you may apply either direction of a -cycle on the chosen indices.

Your task is to determine the minimum number of operations needed to sort the permutation (make p_i=i for all 1 \le i \le n). If it is impossible to sort the permutation using such operations, output .

Input

The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains a single integer (3 \le n \le 10^6) — the length of permutation .

The second line of each test case contains separated integers p_1,p_2,..,p_n (1 \le p_1,p_2,..,p_n \le n) — the permutation .

It's guaranteed that sum of over all tests doesn't exceed 10^6.

Output

For each test case, output a single integer : the minimum number of operations required to sort the permutation , or if impossible.

Examples

Example 1

Loading
Loading

Scoring

  1. Subtask ( points) : (1 \le \sum n \le 5)

  2. Subtask ( points) : (1 \le \sum n \le 10)

  3. Subtask ( points) : (1 \le \sum n \le 100)

  4. Subtask ( points) : is even

  5. Subtask ( points) : No additional constraints