## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Maximum Crossings (Easy Version) Codeforces Solution | Codeforces Problem Solution 2022

H1. Maximum Crossings (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between the two versions is that in this version $n\le 1000$ and the sum of $n$ over all test cases does not exceed $1000$.

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=\left[4,1,4,6,7,7,5\right]$. 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?

Input

The first line contains an integer $t$ ($1\le t\le 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1\le n\le 1000$) — the length of the array.

Most Similar Words Codeforces Solution

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le n$) — the elements of the array.

The sum of $n$ across all test cases does not exceed $1000$.

Output

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