Sakurako‘s Field Trip

Sakurako’s Field Trip

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 i i has some topic of interest which is described as a i a_i ai​. 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 j j ( 1 ≤ j < n 1 \le j < n 1≤j<n) such that a j = a j + 1 a_j = a_{j + 1} aj​=aj+1​.

In order to do this, you can choose index i i i ( 1 ≤ i ≤ n 1\le i\le n 1≤i≤n) and swap students at positions i i i and n − i + 1 n-i+1 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 t t ( 1 ≤ t ≤ 1 0 4 1\le t\le 10^4 1≤t≤104) — the number of test cases.

Each test case is described by two lines.

• The first line contains one integer n n n ( 2 ≤ n ≤ 1 0 5 2 \le n \le 10^5 2≤n≤105) — the length of the line of students.
• The second line contains n n n integers a i a_i ai​ ( 1 ≤ a i ≤ n 1\le a_i\le n 1≤ai​≤n) — the topics of interest of students in line.

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

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

code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#define int long long
 
using namespace std;
 
const int N = 2e5+10,INF=0x3f3f3f3f,mod=1e9+7;
 
typedef pair<int,int> PII;

int T;
int a[N];
int b[N];

void solve(){
	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2,j=n-1;i<j;i++,j--){
		if(a[i]==a[i-1] || a[j]==a[j+1]) swap(a[i],a[j]);
	}
	for(int i=1;i<=n-1;i++){
		if(a[i]==a[i+1]){
			ans++;
		}
	}

	cout<<ans<<endl;
}
 
signed main(){
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}