You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知学校的奖学金是需要去申请的。这天，Z同学在宿舍里接到一个通知，让他去帮助老师完成新生的奖学金申请任务。等Z同学匆匆赶到现场时，他才发现在奖学金申请的地方已经排起了长龙。

题目描述

Z同学数了数排队的同学，发现总共有$n$名同学，并且第$i$位同学拿着一张带有序号$a_{i}$的牌子。他将这一情况讲给老师后，老师说要让同学按照序号从小到大排队，还给了Z同学一张可以无限使用的特效牌。

特效牌功能如下：

1. 每次使用特效牌都可以对准任意一名同学释放一道“命令”，且必定命中。
2. “命令”会使被命中的同学自觉走到队列的最末端。

现在Z同学需要使用特效牌使得队列变得满足老师的要求。

输入格式

第一行输入一个整数$T$，表示有$T$组测试样例。

接下来对于每组测试样例：

• 第一行输入一个整数,表示前来申请奖学金的人数$n$。
• 第二行，输入$n$个整数，第$i$个整数表示排队的第$i$个同学的序号$a_{i}$。（保证$1 \leq a_{i} \leq n$，且不重复）

输出格式

输出$T$行。

对于每组测试样例，输出Z同学使用特效牌的最少次数。

输入输出样例 #1

输入 #1

3
7
5 6 7 1 2 3 4
10
8 9 1 10 4 2 3 6 5 7
6
6 5 4 3 2 1

输出 #1

3
7
5

说明/提示

对于全部测试点，保证$1 \leq T \leq 1000$，$1 \leq n \leq 10000$。

温馨提示：该题目输入量十分庞大，请注意自己的读入方式。

对于c&c++选手，需要使用scanf，或者快读优化的cin，亦或者手写快读函数。