宝石迷阵 (Bejeweled)

题目描述

WIKI 最近迷恋上了宝石迷阵, 她给她最好的朋友 NonFriedChips 出了一道题, 做不出来要狠狠惩罚 NonFriedChips

NonFriedChips 不想被 WIKI 狠狠惩罚, 于是她找到了你, 想让你帮她做出来这道题

注意, 玩过宝石迷阵并不会帮助理解题意, 请仔细阅读, 该题和普通三消规则并不相同

现在有 $n$ 个宝石排成一列, 每个宝石有一个颜色 $a$

每次操作都将进行以下两步

1. 选择不在最后的一个宝石 $i$, 且有宝石颜色标号 $a_i = i$
2. 消除该宝石及它紧邻后面的一个宝石, 消除之后后面的宝石将会向前移动与前面部分相连

请求出你最多能操作的次数

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $t \ (1 \leq t \leq 100)$ —— 测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含一个整数 $n \ (1 \leq n \leq 800)$ —— 宝石的数量

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq n)$ ——每个宝石的颜色

保证所有测试用例中的 $n$ 之和不超过 800

输出

对于每个测试用例，输出一个整数 —— 可以执行操作的最大次数。

样例输入

1
5
1 5 3 2 4

样例输出

2