B. 简单坐椅子

时间限制： 每个测试 1.5 秒 内存限制： 每个测试 256 MB

有 (n) 把椅子排成一排，最初全部未标记。

你得到一个长度为 (n) 的排列 (*)

$p_1, p_2, \dots, p_n$

现在，你玩一个游戏：

1. 从第 1 把椅子开始，依次访问每把椅子。

2. 在第 (i) 把椅子时，可以选择以下操作：

   • 如果该椅子已经被标记，则游戏立即结束，你无法坐下。
   • 否则，你可以选择坐下，或者跳过移动到下一把椅子。
   • 如果你选择坐下，站起来后，你需要标记第 (p_i) 把椅子，然后继续访问下一把椅子。

3. 当所有 (n) 把椅子都被访问后，游戏结束。

你的任务是：计算最多可以坐多少把椅子。

(*) 长度为 (n) 的排列是一个数组，包含从 (1) 到 (n) 的 (n) 个互不相同的整数，顺序可以任意。例如：

• [2,3,1,5,4] 是一个排列
• [1,2,2] 不是排列（2 出现了两次）
• [1,3,4] 不是排列（n=3，但数组中出现了 4）

输入

每个测试包含多组测试数据。 第一行包含一个整数 $(t)（1 ≤ t ≤ 10^4）$，表示测试用例的数量。

接下来每组测试数据描述如下：

• 第一行包含一个整数 (n)$（1 ≤ n ≤ 2⋅10^5$）——椅子数量
• 第二行包含 (n) 个互不相同的整数 $(p_1, p_2, \dots, p_n)$ ——排列 p

保证所有测试用例中 n 的总和 ≤ 2⋅10^5。

输出

每组测试输出一行，包含一个整数 —— 最多可以坐下的椅子数。

样例

输入

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

输出

2
2
3
1

样例说明

• 第一组测试：

  1. 访问第 1 把椅子，坐下并标记第 3 把椅子
  2. 访问第 2 把椅子，坐下并标记第 2 把椅子
  3. 访问第 3 把椅子，已标记 → 游戏结束 → 总共坐 2 把椅子，已达到最大值。

• 第二组测试：

  1. 访问第 1 把椅子，坐下并标记第 4 把椅子
  2. 访问第 2 把椅子，跳过
  3. 访问第 3 把椅子，坐下并标记第 2 把椅子
  4. 访问第 4 把椅子，已标记 → 游戏结束 → 总共坐 2 把椅子，已达到最大值。