1771: 赶上世界崩坏的速度，将你拯救

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：267 解决：77

题目描述



小坚书直实和一行琉璃决定把一行琉璃爷爷的书籍拿出来，在慈善会上卖掉筹集善款。然而在慈善会开幕的前一天晚上被烈火烧成灰烬。小坚书直实不想让一行琉璃伤心，决定用自己的魔法恢复一部分书籍。
但是他的法力还不够，必须得通过解决问题提升法力，才能恢复一部分书籍。
小坚书直实想要请你帮他解决这个难题。
给出 n 个数 ai，每次操作可以去掉其中任意两个数(每次都必须是两个数)，问至少多少次操作后存在一种排序使得剩下的数排序后，在数值上严格递增。

输入

第一行给出 t （ 1 <= t <= 1000 ）
接下来 t 组，每组包括两行，每组的第一行给出一个 n （ 1 <= n <= 50 ），代表数的数量。第二行给出 数值 ai  （ 0 < ai <= 10000 ）。

输出

输出至少多少次操作后存在一种排序使得剩下的数排序后，在数值上严格递增。

样例输入 复制 

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

样例输出 复制 

1
2