Maximum Crossings (Easy Version)

题意翻译

两个版本间唯一的区别是，此版本中 $n≤1000，\sum n≤1000$。 一个终端是一排 $n$ 个连接在一起的相等的线段，有两个终端，一上一下。 有一个数组 $a_i$，代表从上面的终端中第 $i$ 条线段，到下面的终端中第 $a_i$ 条线段，有一条连线。 问这些连线最多有几个交点。

题目描述

The only difference between the two versions is that in this version $ n \leq 1000 $ and the sum of $ n $ over all test cases does not exceed $ 1000 $ . A terminal is a row of $ n $ equal segments numbered $ 1 $ to $ n $ in order. There are two terminals, one above the other. You are given an array $ a $ of length $ n $ . For all $ i = 1, 2, \dots, n $ , there should be a straight wire from some point on segment $ i $ of the top terminal to some point on segment $ a_i $ of the bottom terminal. For example, the following pictures show two possible wirings if $ n=7 $ and $ a=[4,1,4,6,7,7,5] $ . A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red. What is the maximum number of crossings there can be if you place the wires optimally?

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 1000 $ ) — the length of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array. The sum of $ n $ across all test cases does not exceed $ 1000 $ .

输出格式

For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

输入输出样例

输入样例 #1

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

输出样例 #1

6
1
0
3

说明

The first test case is shown in the second picture in the statement. In the second test case, the only wiring possible has the two wires cross, so the answer is $ 1 $ . In the third test case, the only wiring possible has one wire, so the answer is $ 0 $ .