C. Sakurako's Field Trip
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index $$$i$$$ has some topic of interest which is described as $$$a_i$$$. As a teacher, you want to minimise the disturbance of the line of students.

The disturbance of the line is defined as the number of neighbouring people with the same topic of interest. In other words, disturbance is the number of indices $$$j$$$ ($$$1 \le j < n$$$) such that $$$a_j = a_{j + 1}$$$.

In order to do this, you can choose index $$$i$$$ ($$$1\le i\le n$$$) and swap students at positions $$$i$$$ and $$$n-i+1$$$. You can perform any number of swaps.

Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times.

Input

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

Each test case is described by two lines.

  • The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the line of students.
  • The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le n$$$) — the topics of interest of students in line.

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

Output

For each test case, output the minimal possible disturbance of the line that you can achieve.

Example
Input
9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3
Output
1
2
1
0
0
1
1
0
2
Note

In the first example, it is necessary to apply the operation to $$$i=2$$$, thus the array will become $$$[1, \textbf{2}, 1, \textbf{1}, 3]$$$, with the bold elements indicating those that have swapped places. The disturbance of this array is equal to $$$1$$$.

In the fourth example, it is sufficient to apply the operation to $$$i=3$$$, thus the array will become $$$[2, 1, \textbf{2}, \textbf{1}, 2, 4]$$$. The disturbance of this array is equal to $$$0$$$.

In the eighth example, it is sufficient to apply the operation to $$$i=3$$$, thus the array will become $$$[1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]$$$. The disturbance of this array is equal to $$$0$$$.