题目描述

有一个 $n\times n$ 的网格，你可以在网格中放墙 \ 或 /，墙可以改变蜗牛的行进方式（初始没有任何墙）

例如：

现在你的网格上方有 $n$ 只蜗牛，他们起初是向下走的，第 $i$ 只蜗牛在第 1 行第 $i$ 列上方

每只蜗牛对应一个巢穴，巢穴从 1 到 $n$ 编号，第 $i$ 个巢穴在第 $n$ 行第 $i$ 列下方

注意，第$i$ 只蜗牛不一定对应第 $i$ 个巢穴，不存在两只蜗牛对应同一个巢穴

你需要对网格放墙，使得能够走到对应巢穴的的蜗牛数量尽可能的多，输出这个数量

输入格式

第一行一个整数 $T$ ，表示数据组数

对于每组数据

第一行一个整数 $n$ ，表示网格大小

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 只蜗牛对应的巢穴编号

输出格式

共 $T$ 行，第 $i$ 行表示第 $i$ 组数据的答案

样例1

input

4
1 3 2 4

output

3

数据范围

对于 100% 的数据，满足 $1\leq T\leq 10$

对于 15% 的数据，满足 $1\leq n\leq 4$

对于 30% 的数据，满足 $1≤n≤5$

对于 45% 的数据，满足 $1≤n≤100$

对于 100% 的数据，满足 $1≤n≤10^5$