F-红魔馆的微瑕序位_牛客周赛 Round 130

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 帕秋莉的巴瓦鲁魔法图书馆中，有 $n$ 本编号依次为 $1, 2, \dots, n$ 的魔导书。由于魔理沙的“借阅”，这些书现在的排列顺序变成了一个随机的排列 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 为了进行魔法实验，帕秋莉需要调整这排魔导书的顺序。她定义这排书的“混乱度” $S$ 为：

$\displaystyle S = \sum_{i=1}^{n} \Big\lvert a_i - i \Big\rvert$

$\hspace{15pt}$ 帕秋莉认为，当混乱度 $S$ 恰好等于 $2$ 时，图书馆的魔力流向最为稳定。
$\hspace{15pt}$ 十六夜咲夜受命进行调整。她每次操作可以交换任意两本书的位置。请你计算，咲夜最少需要多少次操作，才能使这排魔导书的排列满足混乱度 $S=2$ ？

$\hspace{15pt}$ 保证对所有满足输入约束的数据，存在操作序列使最终混乱度恰为 $2$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示魔导书的数量。
第二行输入  个两两不同的整数 ，表示魔导书当前的排列。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行输出一个整数，表示将混乱度  变为  所需的最少操作次数。

示例1

输入

复制

输出

复制

0
1

说明

对于第一组测试数据，当前的混乱度 。
由于混乱度已经为 ，因此不需要任何操作，输出 。