该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面翻译

题目描述

给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。
你可以对排列 $p$ 进行下列操作任意次：

• 选择整数 $i,j(1\leq i<j\leq n)$，然后交换 $p_i,p_j$ 的值。

你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。
每个测试点包含 $t$ 组数据。

输入格式

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据：
第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。
接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p$ 是一个 $1\sim n$ 的排列。

输出格式

对于每组数据：
输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。
可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

题目描述

You are given a permutation $^\dagger$ $p$ of length $n$ .

In one operation, you can choose two indices $1 \le i < j \le n$ and swap $p_i$ with $p_j$ .

Find the minimum number of operations needed to have exactly one inversion $^\ddagger$ in the permutation.

$^\dagger$ A permutation 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).

$^\ddagger$ The number of inversions of a permutation $p$ is the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$ and $p_i > p_j$ .

输入格式

The first line contains a single integer $t$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ).

The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ( $1 \le p_i \le n$ ). It is guaranteed that $p$ is a permutation.

输出格式

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

样例 #1

样例输入 #1

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

样例输出 #1

0
1
3
1

提示

In the first test case, the permutation already satisfies the condition.

In the second test case, you can perform the operation with $(i,j)=(1,2)$ , after that the permutation will be $[2,1]$ which has exactly one inversion.

In the third test case, it is not possible to satisfy the condition with less than $3$ operations. However, if we perform $3$ operations with $(i,j)$ being $(1,3)$ , $(2,4)$ , and $(3,4)$ in that order, the final permutation will be $[1, 2, 4, 3]$ which has exactly one inversion.

In the fourth test case, you can perform the operation with $(i,j)=(2,4)$ , after that the permutation will be $[2,1,3,4]$ which has exactly one inversion.

【数据范围】

对于 50%的数据，满足 n≤5。

对于 80% 的数据，满足 n≤1000。

对于 100% 的数据，满足 1≤𝑛≤100000，1≤𝑡≤5。