题目描述

青在数据中心调试一条重要的信号序列，这条序列由 $n$ 个整数单元组成，记为 $a_1, a_2, \dots, a_n$。

由于传输干扰，序列可能不符合解码规范。青定义了一种可解码序列，它必须满足以下结构：

• 序列可以被分割成若干个连续的信号块。
• 每个信号块的第一单元表示该块的长度 $L$（$L \ge 1$），紧接着的 $L$ 个单元属于该块的内容。
• 例如，序列 $[3, 3, 4, 5, 2, 6, 1]$ 和 $[1, 8, 4, 5, 2, 6, 1]$ 是可解码的（不同块用颜色区分），而 $[1]$、$[1, 4, 3]$、$[3, 2, 1]$ 则不是。

为了优化序列，青可以进行清理操作：每次选择序列中的任意一个单元，将其移除。

青想知道，至少需要多少次清理操作，才能将原始信号序列调整为可解码序列？

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^6$）—— 序列 $a$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个数字 —— 使序列 $a$ 调整为可解码序列的最少清理操作次数。

输入输出样例 #1

输入 #1

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

输出 #1

0
4
1
1
2
1
0

说明/提示