H1. Максимизация пересечений (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственная разница между двумя версиями состоит в том, что в этой версии $$$n \leq 1000$$$ и сумму значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$1000$$$.

Терминал — это ряд без промежутков из $$$n$$$ равных отрезков, пронумерованных от $$$1$$$ до $$$n$$$ по порядку. Есть два терминала, один над другим.

Вам дан массив $$$a$$$ длины $$$n$$$. Для всех $$$i = 1, 2, \dots, n$$$ должен быть прямой провод из некоторой точки на отрезке $$$i$$$ верхнего терминала в некоторую точку на отрезке $$$a_i$$$ нижнего терминала. Например, на следующих рисунках показаны два возможных соединения, при $$$n=7$$$ и $$$a=[4,1,4,6,7,7,5]$$$.

Пересечение происходит, когда два провода имеют общую точку. На картинке выше пересечения обведены красным.

Какое максимальное количество пересечений может быть при оптимальном размещении проводов?

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — длина массива.

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

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

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

Первый пример показан на втором рисунке в условии.

Во втором примере при единственно возможном соединении появляется пересечение двух проводов, поэтому ответ равен $$$1$$$.

В третьем тестовом примере единственно возможное соединение состоит из одного провода, поэтому ответ равен $$$0$$$.