题目内容

在一排编号为 $1$ 到 $n$ 的房间里，你正站在房间 $1$ 处，目标是最快抵达房间 $n$。 每个房间都有两种移动方式：

• 使用房间内的跃迁装置：可以瞬间转移到指定的另一个房间 $a_i$，不消耗体力；
• 如果当前不是最后一个房间，可以向右步行到相邻的 $i+1$ 号房间，消耗 $1$ 单位体力。

你需要求出从房间 $1$ 出发到达房间 $n$ 所需的最小体力消耗。

数据约束：

• 测试数据组数 $q$ 不超过 $10^5$；
• 每组数据的房间数 $n$ 不超过 $5 \times 10^5$，且全部 $n$ 的总和不超过 $5 \times 10^5$；
• 每个跃迁目标 $a_i$ 满足 $1 \le a_i \le n$。

输入描述

第一行包含一个整数 $q$，表示测试数据的组数。 接下来依次输入每组数据，每组格式如下： 第一行包含一个整数 $n$，表示房间数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示从房间 $i$ 使用跃迁装置后到达的房间编号。

输出描述

对于每组数据，输出一行一个整数，表示从房间 $1$ 到房间 $n$ 所需的最小体力消耗。

样例1

输入

1
1
1

输出

0

说明

房间总数 $n=1$，你已经在房间 1，目标也是房间 1，不需要任何移动，体力消耗为 $0$。

样例2

输入

1
3
1 3 2

输出

1

说明

房间编号 $1$ 到 $3$，跃迁目标依次为 $a_1=1$, $a_2=3$, $a_3=2$。 从房间 $1$ 出发：跃迁到 $1$ 无意义，只能向右步行到房间 $2$，消耗 $1$ 体力。 在房间 $2$：使用跃迁装置可直接到达房间 $3$，消耗 $0$ 体力。 总最小体力消耗为 $1$。

样例3

输入

1
4
1 3 2 4

输出

2

说明

房间数 $n=4$，跃迁目标 $a=[1,3,2,4]$。 从房间 $1$ 出发：跃迁到 $1$ 无效，步行到房间 $2$，消耗 $1$。 在房间 $2$：跃迁到房间 $3$，消耗 $0$。 在房间 $3$：跃迁回房间 $2$ 无助于前进，只能步行到房间 $4$，再消耗 $1$。 总最小体力消耗为 $1+1=2$。注意：若尝试其他顺序，无法得到更优解。