F2. Интересная задача (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между простой и сложной версиями задачи заключается только в ограничении на $$$n$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Дан массив целых чисел $$$a$$$ длины $$$n$$$.

Вы можете выполнять следующую двухшаговую операцию:

  1. Выбрать индекс $$$i$$$ такой, что $$$1 \le i < |a|$$$ и $$$a_i = i$$$.
  2. Удалить $$$a_i$$$ и $$$a_{i+1}$$$ из массива и соединить оставшиеся части.

Найдите максимальное количество раз, которое можно применить данную операцию.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 800$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$800$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество раз, которое можно применить операцию из условия.

Пример
Входные данные
6
5
1 5 3 2 4
8
2 1 3 4 5 6 7 8
3
1 2 3
4
1 2 4 4
5
4 4 1 3 5
1
1
Выходные данные
2
3
1
2
0
0
Примечание

В первом наборе входных данных одна из возможных оптимальных последовательностей применения операций такая: $$$[ 1, 5, \color{red}{3}, \color{red}{2}, 4 ] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]$$$.

В третьем наборе входных данных, одна из возможных оптимальных последовательностей применения операций такая: $$$[1, \color{red}{2}, \color{red}{3}] \rightarrow [1]$$$.