题目内容

共享单车停车场有编号 1 到 $n$ 的 $n$ 个停车桩，最初全部离线。调度序列 $a$ 是长度为 $n$、元素两两不同的排列，表示按时间依次唤醒这些桩。第一次唤醒可以免费完成；之后唤醒 $a_i$ 时，若存在已在线且编号满足 $|a_i-x|=1$ 的桩 $x$，则可沿相邻线路免费上线，否则必须消耗 1 次独立调度。必须按给定顺序唤醒全部停车桩，并使独立调度次数尽可能少。请输出该最少次数。

约束：测试组数不超过 10000；单组桩数不超过 200000；单个文件中所有 $n$ 之和不超过 200000；$a$ 是 1 到 $n$ 的排列。

输入描述

第一行一个整数 $t$，表示测试组数。 每组数据：第一行一个整数 $n$；第二行 $n$ 个两两不同的整数 $a_1,a_2,\ldots,a_n$。 保证 $1 \le t \le 10000$，$1 \le n \le 200000$，$1 \le a_i \le n$，且单个测试文件中所有 $n$ 之和不超过 200000。

输出描述

对每组数据输出一行一个整数，表示最少独立调度次数。

样例1

输入

3
1
1
4
2 4 1 3
6
1 3 5 2 4 6

输出

0
1
2

说明

三组：

• $n=`1`$：首次点亮免费，独立点火 0 次；
• 顺序 $2,4,1,3$：点亮 4 时与已亮的 2 不相邻，点火 1 次，其余可衔接；
• 顺序 $1,3,5,2,4,6$：点亮 3、5 时各点火一次，共 2 次。

样例2

输入

1
5
4 2 5 1 3

输出

1

说明

顺序 $4,2,5,1,3$：首次点亮 4 免费；点亮 2 时与 4 不相邻，点火 1 次；随后 5 与 4 相邻，1、3 也可衔接。答案为 1。