描述

“哦不，他们又搞砸了。”晶圆厂（Waferland chip factory）的首席设计师喊道。布线设计师们又一次彻底搞砸了，芯片上连接两个功能模块端口的信号到处相互交叉。在这个流程的后期，重新布线的成本太高了。作为替代，工程师们必须使用三维空间来桥接信号，以确保没有两个信号相互交叉。然而，桥接是一个复杂的操作，因此希望尽可能少地桥接信号。此时迫切需要一个计算机程序，该程序能够找出在芯片表面上不相互交叉的信号的最大数量。考虑到一个功能模块的边界可能有数千个信号端口，这个问题对程序员来说要求颇高。你能完成这项任务吗？

一个典型的情况如图1所示。两个功能模块的端口从上到下编号为1到p。信号映射由1到p的数字的一个排列描述，形式为一个包含p个唯一数字的列表，其中第i个数字指定右侧的哪个端口应连接到左侧的第i个端口。当且仅当连接每对端口的直线交叉时，两个信号交叉。

输入

输入的第一行是一个正整数n，表示接下来测试场景的数量。每个测试场景的第一行包含一个正整数p，且p < 40000，表示两个功能模块上的端口数量。然后是p行，描述信号映射：第i行是右侧功能模块上应连接到左侧功能模块的第i个端口的端口号。

输出

对于每个测试场景，输出一行，包含在芯片表面上不相互交叉的信号的最大数量。

输入示例1

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

输出示例1

3
9
1
4

来源

2003年西北欧区域赛