The Language of Westeros

Input

The first line contains an integer $t$ (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ (1 \le n \le 4 \cdot 10^5, 1 \le m \le 2 \cdot 10^5) — the length of the array and the number of letters in the alphabet.

The next line contains an array of integers $a$ of length $n$ (1 \le a_i \le m) — the array Bran Stark came across.

It is guaranteed that the sum of $n$ over all test cases does not exceed 4 \cdot 10^5.

Output

For each query, output one number — the minimum number of the described operations required to transform the array into a palindrome.

Examples

Note

Explanation for the first test case

In the first example, one can first shuffle the letters into the order [2,4,6,9,7,5,2], then move the second letter clockwise and the fifth letter counterclockwise, obtaining the array [2,5,6,9,6,5,2], which is a palindrome.

In the second example, after first shuffling the letters into the order [1,3,2,1,1,3,3,1], and then moving the third letter clockwise, we obtain the array [1,3,3,1,1,3,3,1], which is a palindrome.

Scoring

1. Subtask $1$ ($25$ points): (n\le 10)

2. Subtask $2$ ($35$ points): (m \le 2)

3. Subtask $3$ ($50$ points): $(n$ — even)

4. Subtask $4$ ($60$ points): (n \le 100)

5. Subtask $5$ ($130$ points): No additional constraints