题目背景

在 25w16a 更新中，不再只有玩家可以用拴绳牵引生物，现在生物和生物之间可以用拴绳连接在一起，一个连一个，然后被善魂带上天...... （哇哦！）

题目描述

Hojstyer 把善魂当成热气球，用拴绳在下面吊了一串铁傀儡、熊猫、狼、狐狸、劫掠兽、爬行者和豹猫 —— 简直是世界奇观！

但是把一堆大家伙串起来还是太反直觉了，Hojstyer 希望按体重调换一下生物的顺序，使整条拴绳上的生物能从轻到重排好队。由于松开拴绳的生物会到处乱跑，所以他决定每次只交换两个生物的位置，已知 n 个生物先前的顺序，他想知道怎么样交换生物最简单。

形式上，给定一个长度为 n 的排列 p，每次你可以执行以下操作：

• 选择两个不同的下标 1 \leq i < j \leq n
• 交换 p_i, p_j

求使用最少的操作次数使得排列递增。

每个测试文件由多个测试用例组成。第一行包含一个整数 t (1 \leq t \leq 10^5) 表示测试用例数。

对于每个测试用例，第一行输入一个整数 n (1 \leq n \leq 2 \times 10^5) - 排列 p 的长度。

第二行输入 n 个整数, 第 i 个整数表示 p_i (1 \leq p_i \leq n)，保证 p 是一个排列。

数据保证所有测试用例中 n 的总和不超过 2\times 10^5。

对于每个测试用例，输出一个非负整数, 表示能使得排列单增的最少操作次数。

在第 1 个测试用例中，排列已经有序，无需操作。

在第 2 个测试用例中，我们可以进行以下 3 次操作:

• 将 p_2 和 p_4 交换，此时排列变成 [1, 2, 5, 3, 4];
• 将 p_3 和 p_4 交换，此时排列变成 [1, 2, 3, 5, 4];
• 将 p_4 和 p_5 交换，此时排列变成 [1,2,3,4,5];
• 可以证明没有更少操作次数的解。

在第 3 个测试用例中，我们可以进行以下 2 次操作:

• 将 p_1 和 p_4 交换，此时排列变成 [1, 3, 2, 4];
• 将 p_2 和 p_3 交换，此时排列变成 [1, 2, 3, 4];
• 可以证明没有更少操作次数的解。