你在算法课上刚学到了一种排序数组的新方法。该算法通过重复执行“删除并追加”（Delete-and-Append）操作来对数组进行排序。“删除并追加”操作包含以下三个步骤：

1) 从数组中选择一个元素。 2) 从数组中删除该元素。 3) 将该元素追加到数组末尾。

作为一个好奇的学生，你想知道将给定数组排序所需的最少“删除并追加”操作次数是多少。

输入格式

输入的第一行包含一个十进制整数 $P$ ($1 \le P \le 100$)，表示随后数据组的数量。每组数据应被独立且相同地处理。

每组数据由两行或多行输入组成。第一行包含数据组编号 $K$，后跟一个空格，再后跟一个整数 $N$ ($1 \le N \le 1000$)，表示待排序数组的长度。接下来的行包含组成待排序数组的 $N$ 个正整数，每行 10 个数值，最后一行可能少于 10 个数值。所有数组元素均不超过 $10^9$。待排序数组中可能出现重复值。

输出格式

对于每组数据，输出一行。该行包含数据组编号 $K$，后跟一个空格，再后跟一个整数，表示将数组排序所需的最少“删除并追加”操作次数。

样例

输入 1

3
1 3
1 3 2
2 6
1 5 2 4 3 6
3 23
67890 56312 999999999 12345 23456 
38927 45632 100345 98765 23456
87654 43278 23456 117654 321899 
25432 54326 217435 26845 31782
33456 41234 56213

输出 1

1 1
2 3
3 15