You are given an array $a$ of length $n$. We define the equality of the array as the number of indices $1 \le i \le n - 1$ such that $a_i = a_{i + 1}$. We are allowed to do the following operation:

Select two integers $i$ and $x$ such that $1 \le i \le n - 1$ and $1 \le x \le 10^9$. Then, set $a_i$ and $a_{i + 1}$ to be equal to $x$.

Find the minimum number of operations needed such that the equality of the array is less than or equal to $1$.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10 ^ 5$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.

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


-----Output-----

For each test case, print the minimum number of operations needed.


-----Examples-----

Input
4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4
Output
2
1
2
0


-----Note-----

In the first test case, we can select $i=2$ and $x=2$ to form $[1, 2, 2, 1, 1]$. Then, we can select $i=3$ and $x=3$ to form $[1, 2, 3, 3, 1]$.

In the second test case, we can select $i=3$ and $x=100$ to form $[2, 1, 100, 100, 2]$.

Difficulty: EASY
Tags: Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
amountCases = int(sys.stdin.readline())
for case in range(amountCases):
	size = int(sys.stdin.readline())
	list = sys.stdin.readline().strip().split()
	start = -1
	end = -1
	for i in range(len(list) - 1):
		if list[i] == list[i + 1]:
			end = i + 1
			if start == -1:
				start = i
	minOp = end - start - 2
	if end - start <= 1:
		minOp = 0
	if end - start == 2:
		minOp = 1
	sys.stdout.write(str(minOp) + '\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = input()[:-1].split()
	(d, e) = (n, 0)
	for i in range(1, n):
		if w[i] == w[i - 1]:
			d = i
			break
	for i in range(n - 2, d - 1, -1):
		if w[i] == w[i + 1]:
			e = i
			break
	print(max(0, e - d) if d != e else 1)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	m = n + 5
	M = -1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			m = min(m, i)
			M = i
	if M < 0 or m == M:
		print(0)
	elif M - m <= 2:
		print(1)
	else:
		print(M - m - 1)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
sys.setrecursionlimit(10000)

def read_line(f):
	while True:
		s = f.readline().strip()
		if s:
			return s

def read_list(f):
	return [int(x) for x in read_line(f).split()]

def read_tuple(f):
	return tuple(read_list(f))

def load_single_case(f):
	read_line(f)
	return read_list(f)

def load_cases(f):
	n = int(f.readline())
	cases = []
	for _ in range(n):
		yield load_single_case(f)
	return cases

def solve(case):
	ai = case
	pf = None
	pl = None
	for i in range(len(ai) - 1):
		if ai[i] == ai[i + 1]:
			if pf is None:
				pf = i + 1
			pl = i
	if pl is None or pl < pf:
		return 0
	return max(1, pl - pf)

def outcome_string(outcome):
	return '{}'.format(outcome)

def save_outcomes(f, outcomes):
	for (n, o) in enumerate(outcomes):
		f.write('{}\n'.format(outcome_string(o)))

def process(path_in=None, path_out=None):
	if path_out is None and path_in is not None:
		path_out = path_in.rsplit('.', 1)[0] + '.out'
	f_in = open(path_in) if path_in else sys.stdin
	f_out = open(path_out, 'w') if path_out else sys.stdout
	try:
		outcomes = [solve(c) for c in load_cases(f_in)]
		save_outcomes(f_out, outcomes)
	finally:
		if path_in:
			f_in.close()
		if path_out:
			f_out.close()
process()


def Input():
	global l2
	n = int(input())
	l2 = []
	for i in range(n):
		t = int(input())
		l = [int(x) for x in input().split()]
		l2.append(l)

def main():
	for i in l2:
		ind1 = 0
		ind2 = 0
		for j in range(len(i) - 1):
			if i[j] == i[j + 1]:
				ind1 = j + 1
				break
		i = i[::-1]
		for j in range(len(i) - 1):
			if i[j] == i[j + 1]:
				ind2 = len(i) - j - 2
				break
		if ind1 == 0:
			print(0)
		elif ind2 - ind1 == -1:
			print(0)
		elif ind2 == ind1:
			print(1)
		else:
			print(ind2 - ind1)
Input()
main()


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = 0
	d = -1
	e = -1
	for j in range(1, a):
		if b[j] == b[j - 1]:
			c += 1
			e = j
			if d == -1:
				d = j - 1
	if c < 2:
		print(0)
	elif e - d < 4:
		print(1)
	else:
		print(e - d - 2)


t = int(input())
out = ''
for _ in range(t):
	size = int(input())
	arr = [int(x) for x in input().split()]
	first = -1
	last = -1
	for i in range(1, len(arr)):
		if arr[i] == arr[i - 1]:
			if first == -1:
				first = i
			else:
				last = i - 1
	if last == first and first != -1:
		out += '1\n'
		continue
	out += str(max(0, last - first)) + '\n'
print(out)


t = int(input())
for i in range(t):
	l = int(input())
	v = input().split()
	j = 1
	fi = -1
	la = -1
	while j < len(v):
		if v[j - 1] == v[j]:
			la = j - 1
			if fi == -1:
				fi = j - 1
		j += 1
	if fi == -1:
		print(0)
	elif fi == la:
		print(0)
	elif la == fi + 1:
		print(1)
	else:
		print(la - fi - 1)


def _NO():
	print('NO')

def _YES():
	print('YES')

def _int_list_input():
	return list(map(int, input().split()))

def solve():
	n = int(input())
	a = _int_list_input()
	first_double_idx = -1
	last_double_idx = -1
	for i in range(0, n - 1):
		if a[i] == a[i + 1]:
			if first_double_idx == -1:
				first_double_idx = i
			last_double_idx = i
	if last_double_idx - first_double_idx < 2:
		print(last_double_idx - first_double_idx)
	else:
		print(last_double_idx - first_double_idx - 1)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
import sys
if sys.argv[0] in ['main.py']:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
main()


t = int(input())
res = []

def KT(arr):
	k = 0
	for i in range(len(arr) - 1):
		if arr[i] == arr[i + 1]:
			k = k + 1
	return k
for i in range(t):
	n = int(input())
	inp = input().split()
	a = [int(ai) for ai in inp]
	if KT(a) <= 1:
		res.append(0)
	else:
		firstFlag = 0
		for ai in range(len(a) - 1):
			if a[ai] == a[ai + 1]:
				firstFlag = ai + 1
				break
		k = len(a) - 1
		lastFlag = k
		while k >= 0:
			if a[k] == a[k - 1]:
				lastFlag = k - 1
				break
			k = k - 1
		if firstFlag == lastFlag:
			res.append(1)
		else:
			res.append(lastFlag - firstFlag)
for item in res:
	print(item)


import math
import collections
import itertools
import functools

def fun(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	lo = -1
	hi = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			lo = i - 1
			break
	for i in range(lo + 1, n):
		if a[i] == a[i - 1]:
			hi = i
	if hi != lo + 1 and lo != -1:
		print(max(1, hi - lo - 2))
	else:
		print('0')
for tc in range(int(input())):
	fun(tc)


t = int(input())

def solve(n, lst):
	left_flag = False
	right_flag = False
	left_ind = -1
	right_ind = -1
	for i in range(len(lst) - 1):
		if lst[i] == lst[i + 1]:
			if left_flag == False:
				left_flag = True
				left_ind = i
			else:
				right_flag = True
				right_ind = i
	if right_flag == False:
		return 0
	elif right_ind - left_ind <= 2:
		return 1
	else:
		return right_ind - left_ind - 1
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from sys import stdin, stdout
import io
import math
import heapq
import bisect
import collections

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')

def get():
	return stdin.readline().rstrip()
mod = 10 ** 5 + 7
for _ in range(int(get())):
	n = int(get())
	l = list(map(int, get().split()))
	a = [-1, -1]
	b = [-1, -1]
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			a[0] = i
			a[1] = i + 1
			break
	for i in range(n - 1, 0, -1):
		if l[i] == l[i - 1]:
			b[0] = i - 1
			b[1] = i
			break
	f = 0
	x = 0
	for j in range(a[0], b[1] + 1):
		if l[j] != l[a[0]]:
			f = 1
		else:
			x += 1
	if a == b:
		print(0)
	elif f == 0:
		if x - 2 == 1:
			print(1)
		else:
			print(x - 3)
	else:
		print(b[0] - a[1])


T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	(start, end) = (-1, -1)
	for i in range(len(A) - 1):
		if A[i] == A[i + 1]:
			if end == -1:
				start = i
				end = i
			else:
				end = i
	if end == start:
		ans = 0
	elif end - start == 1:
		ans = 1
	else:
		ans = end - (start + 1)
	print(ans)


def res(a):
	(l, r) = (None, None)
	c = 0
	for i in range(len(a) - 1):
		if a[i] == a[i + 1]:
			c += 1
			if l is None:
				l = i
			else:
				r = i
	if c < 2:
		return 0
	else:
		return r - l - 1 if r - 1 > l else 1

def main():
	for _ in range(int(input())):
		input()
		a = list(map(int, input().split()))
		print(res(a))
main()


t = int(input())
for j in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	ld = []
	ls = []
	a = 0
	b = 0
	s = 0
	q = 0
	d = 0
	for i in range(n - 1):
		if m[i] == m[i + 1]:
			a = i + 1
			break
	if a == 0:
		print(0)
		continue
	for i in range(n - 1, 0, -1):
		if m[i - 1] == m[i]:
			b = i - 1
			break
	if b <= a:
		a -= 1
	print(b - a)


def check(x, y):
	pairs_cou = 0
	pairs = []
	for i in range(0, x - 1):
		if y[i] == y[i + 1]:
			pairs_cou += 1
			pairs.append([i, i + 1])
	if pairs_cou < 2:
		return '0'
	else:
		a = pairs[0][1]
		b = pairs[-1][0]
		c = b - a
		if c == 0:
			c += 1
		return c
t = int(input())
for i in range(t):
	x = int(input())
	y = list(map(int, input().split()))
	print(check(x, y))


def solve(a):
	(left, right) = (-1, -1)
	for i in range(len(a) - 1):
		if a[i] == a[i + 1]:
			left = i
			break
	for i in range(len(a) - 2, i, -1):
		if a[i] == a[i + 1]:
			right = i
			break
	if left > -1 and right > -1:
		return max(right - left - 1, 1)
	return 0
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(s) for s in input().split(' ')]
	print(solve(a))


def solve():
	if n < 3:
		return 0
	left_ind = 0
	right_ind = 0
	for i in range(n - 1, 0, -1):
		if arr[i] == arr[i - 1]:
			right_ind = i - 1
			break
	if right_ind == 0:
		return 0
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			left_ind = i + 1
			break
	if right_ind - left_ind == -1:
		return 0
	if right_ind - left_ind == 0:
		return 1
	res = right_ind - left_ind
	return res
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


cases = int(input(''))
tests = []
for i in range(0, cases):
	l = int(input(''))
	arr = [int(i) for i in input('').split(' ')]
	tests.append((l, arr))
for (l, arr) in tests:
	first_pair = None
	second_pair = None
	i = 0
	j = 1
	while True:
		if j == l:
			break
		elif arr[i] != arr[j]:
			i += 1
			j += 1
		else:
			first_pair = (i, j)
			break
	i = l - 2
	j = l - 1
	while True:
		if i < 0:
			break
		elif arr[i] != arr[j]:
			i -= 1
			j -= 1
		else:
			second_pair = (i, j)
			break
	if first_pair == second_pair or first_pair == None or second_pair == None:
		print(0)
		continue
	else:
		if second_pair[0] - first_pair[0] == 1:
			print(1)
			continue
		print(second_pair[0] - first_pair[1])


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	l = -1
	r = -1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			if l == -1:
				l = i
			r = i
	if l == r:
		print(0)
	else:
		print(max(1, r - l - 1))


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	(left, right) = (-1, -1)
	for i in range(1, n):
		if a[i] == a[i - 1]:
			if left == -1:
				left = i
			right = i
	if left == right:
		print(0)
	else:
		print(max(right - left - 1, 1))
for t in range(int(input())):
	solve()


from collections import Counter, deque
from collections import OrderedDict, defaultdict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	A = get.int()
	first = -1
	last = -1
	for i in range(n - 1):
		if A[i] == A[i + 1]:
			if first == -1:
				first = i
			last = i
	if first == -1:
		print(0)
		return
	x = last - first
	if x == 0:
		print(0)
	elif x <= 2:
		print(1)
	else:
		print(x - 1)
t = int(input())
for tt in range(t):
	solve()


def solve(n, arr):
	l = -1
	r = -1
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			if l == -1:
				l = i
			r = i
	if l == r:
		return 0
	return max(1, r - l - 1)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


x = int(input())

def cal(n, arr):
	a = -1
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			a = i
			break
	if a == -1:
		return 0
	b = -1
	for j in range(n - 2, -1, -1):
		if arr[j] == arr[j + 1]:
			b = j
			break
	if b == a:
		return 0
	if b - a == 1:
		return 1
	else:
		return b - a - 1
for jj in range(x):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, arr))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	x = 0
	y = l[0]
	for i in range(n):
		if l[i] == y:
			x = x + 1
		else:
			a.append(x)
			x = 1
			y = l[i]
	a.append(x)
	j = None
	k = None
	for i in range(len(a)):
		if a[i] != 1:
			j = i
			break
	for i in range(len(a) - 1, -1, -1):
		if a[i] != 1:
			k = n - (len(a) - i)
			break
	if k != None and j != None:
		h = k - j + 1
		if h == 1 or h == 2 or h == 0:
			print(0)
		elif h == 3:
			print(1)
		else:
			print(h - 3)
	else:
		print(0)


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	c = []
	for i in range(0, n - 1):
		if a[i] == a[i + 1]:
			c.append(i)
	if len(c) < 2:
		print(0)
	elif c[0] - c[-1] == -1:
		print(1)
	else:
		print(c[-1] - 1 - c[0])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	i = 0
	while i < n - 1:
		if l[i] == l[i + 1]:
			break
		i += 1
	j = n - 1
	while j > 0:
		if l[j] == l[j - 1]:
			break
		j -= 1
	if j - i < 2:
		print(0)
	elif j - i == 2 or j - i == 3:
		print(1)
	else:
		print(j - i - 2)


for inh in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(st, en) = (-1, -1)
	jj = False
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			if jj:
				en = i
			else:
				st = i
				en = i
				jj = True
	if st == en:
		print(0)
	else:
		ans = en - st
		if ans >= 2:
			ans -= 1
		print(ans)


def ss(t, n):
	mn = float('inf')
	mx = -float('inf')
	for i in range(n - 1):
		if t[i] == t[i + 1]:
			mn = min(mn, i)
			mx = max(mx, i)
	if mx - mn == 1:
		return 1
	return max(0, mx - mn - 1)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(ss(l, n))


loopcount = int(input())
for loop in range(loopcount):
	a = int(input())
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	start = 0
	end = 0
	for i in range(a - 1):
		if x[i] == x[i + 1]:
			start = i
			break
	for i in range(a - 1, 1, -1):
		if x[i] == x[i - 1]:
			end = i
			break
	if end - start <= 1:
		print(0)
	else:
		print(max(1, end - start - 2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pairs = []
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			pairs.append(i)
	if len(pairs) <= 1:
		print(0)
	else:
		ans = max(1, pairs[-1] - pairs[0] - 1)
		print(ans)


import sys
s = int(input())
for i in range(s):
	size = int(input())
	arr = list(map(int, input().split()))
	(l, r) = (-1, -1)
	for i in range(1, size):
		if arr[i] == arr[i - 1]:
			if l == -1:
				l = i
			r = i
	if l == r:
		print(0)
	else:
		print(max(1, r - l - 1))


for j in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	highest = 0
	found = False
	for j in range(n - 1):
		if nums[j] == nums[j + 1]:
			if not found:
				lowest = j + 1
			highest = j
			found = True
	if not found:
		print(0)
		continue
	if highest == lowest - 1:
		print(0)
		continue
	if highest == lowest:
		print(1)
		continue
	print(highest - lowest)


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	l = r = -1
	for i in range(N - 1):
		if a[i] == a[i + 1]:
			if l == -1:
				l = i
			r = i
	print(0 if l == r else max(1, r - l - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = r = -1
	for i in range(1, n):
		if a[i - 1] == a[i]:
			if l == -1:
				l = i
			r = i
	if l == r:
		print(0)
		continue
	print(max(1, r - l - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = -1
	y = -1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			if x == -1:
				x = i
			y = i
	if x == y:
		print(0)
	else:
		print(max(1, y - x - 1))


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	st = []
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			st.append(i + 1)
	if len(st) <= 1:
		print(0)
	else:
		print(max(1, st[-1] - 1 - st[0]))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	l = -1
	for j in range(n - 1):
		if lst[j] == lst[j + 1]:
			l = j
			break
	if l == -1:
		print(0)
	else:
		lst1 = lst[::-1]
		r = -1
		for j in range(n - 1):
			if lst1[j] == lst1[j + 1]:
				r = j
				break
		r = n - r - 1
		dif = r - l
		if dif < 2:
			print(0)
		elif dif == 2:
			print(1)
		else:
			d = dif - 2
			c = d
			print(c)


T = int(input())
for case in range(T):
	n = int(input())
	a = map(int, input().strip().split())
	first_duplicate = -1
	last_duplicate = -1
	found_first = False
	prev = -1
	for (i, ai) in enumerate(a):
		if ai == prev:
			last_duplicate = i
			if not found_first:
				first_duplicate = i
				found_first = True
		prev = ai
	ops = 0
	if first_duplicate != last_duplicate:
		ops += max(last_duplicate - first_duplicate - 1, 1)
	print(ops)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	points = [i for i in range(len(a) - 1) if a[i] == a[i + 1]]
	if len(points) <= 1:
		ans = 0
	elif points[-1] - points[0] == 1:
		ans = 1
	else:
		ans = points[-1] - points[0] - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(pl, pr) = (None, None)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			pl = i
			break
	for i in range(n - 1, 0, -1):
		if a[i] == a[i - 1]:
			pr = i
			break
	if pr != None and pl != None:
		if pr - pl == 1:
			print(0)
		elif pr - pl == 2:
			print(1)
		else:
			print(pr - pl - 2)
	else:
		print(0)


import math
for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ctr = 0
	p = s[0]
	st = 0
	st_flag = True
	en = 0
	for i in range(1, len(s)):
		if p == s[i]:
			if st_flag:
				st_flag = False
				st = i - 1
			en = i
			ctr += 1
		p = s[i]
	if ctr >= 2:
		if en - st == 2:
			print(1)
		else:
			print(en - st - 2)
	else:
		print(0)


test = int(input())
for i in range(test):
	n = int(input())
	string = str(input()).split(' ')
	lst = []
	for i in range(n):
		if i < n - 1:
			if string[i] == string[i + 1]:
				lst.append(i + 1)
	if len(lst) == 1:
		print(0)
	elif len(lst) == 0:
		print(0)
	elif max(lst) - min(lst) == 1:
		print(1)
	else:
		print(max(lst) - min(lst) - 1)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		eq = 0
		for i in range(n - 1):
			if ls[i] == ls[i + 1]:
				eq += 1
		(a, b) = (0, 0)
		for i in range(n - 1):
			if ls[i] == ls[i + 1]:
				a = i + 1
				break
		for i in range(n - 1, 1, -1):
			if ls[i] == ls[i - 1]:
				b = i - 1
				break
		df = b - a
		if df == 0:
			df += 1
		print(0 if eq <= 1 else df)
main()


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	start = 0
	end = 0
	for i in range(n - 1):
		if q[i] == q[i + 1]:
			start = i
			break
	for i in range(n - 1, 0, -1):
		if q[i] == q[i - 1]:
			end = i
			break
	if end - start + 1 == 3:
		print(1)
	else:
		print(max(end - start + 1 - 3, 0))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = 0
	r = n - 1
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			l += 1
			break
		else:
			l += 1
	for i in range(n - 1, 0, -1):
		if arr[i] == arr[i - 1]:
			r = r - 1
			break
		else:
			r -= 1
	if l == r:
		print('1')
	elif l < r:
		print(r - l)
	elif l == n - 1 and r == 0:
		print('0')
	else:
		print('0')


a = int(input())
for i in range(a):
	x = 0
	y = 0
	c = int(input())
	d = input().split()
	b = [*map(int, d)]
	for j in range(c - 1):
		if b[j] == b[j + 1]:
			x = j + 1
			break
	for k in range(c - 1):
		if b[c - k - 1] == b[c - k - 2]:
			y = k + 1
			break
	if x + y == 0:
		print(0)
	elif c - x - y == 1 or c - x - y == 0:
		print(c - x - y)
	else:
		print(c - x - y - 1)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	f = 0
	b = 0
	for i in range(N - 1):
		if A[i] == A[i + 1]:
			f = i
			break
	for i in range(N - 1, 0, -1):
		if A[i] == A[i - 1]:
			b = i
			break
	if b - f < 2:
		print(0)
	elif b - f == 2:
		print(1)
	else:
		print(b - f - 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	op = 0
	j = []
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			j.append(i)
	if len(j) > 1:
		op = j[-1] - j[0]
	else:
		op = 0
	if op > 1:
		op = op - 1
	print(op)


t = int(input())
for q in range(t):
	x = int(input())
	a = [int(z) for z in input().split()]
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			break
	for j in range(len(a) - 2, -1, -1):
		if a[j] == a[j + 1]:
			break
	if i > j:
		print(0)
	elif i == j:
		print(1)
	else:
		print(j - i)


import math
for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	a = -1
	e = -1
	for k in range(1, n):
		if A[k] == A[k - 1]:
			if a == -1:
				a = k
			e = k - 1
	if a == -1:
		print(0)
	elif e + 1 == a:
		print(0)
	elif e == a:
		print(1)
	else:
		print(e - a)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (-1, -1)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			if l == -1:
				l = i
			r = i
	print(0 if l == r else max(1, r - l - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [a[i] == a[i + 1] for i in range(n - 1)]
	try:
		x0 = a.index(True)
	except ValueError:
		print(0)
		continue
	x1 = n - 2 - list(reversed(a)).index(True)
	d = x1 - x0
	if d == 0:
		print(0)
	elif d == 1:
		print(1)
	else:
		print(d - 1)


a = int(input())
for i in range(a):
	b = int(input())
	arr = input()
	c = list(map(int, arr.split()))
	j = 0
	y = []
	for k in range(b - 1):
		if c[k] == c[k + 1]:
			y.append(k)
		else:
			y = y
	if len(y) <= 1:
		print(0)
	elif y[len(y) - 1] - y[0] - 1 == 0:
		print(1)
	else:
		print(y[len(y) - 1] - y[0] - 1)


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	b = -1
	l = -1
	for i in range(n):
		if b == -1 and i != n - 1 and (arr[i] == arr[i + 1]):
			b = i
		if i != 0 and arr[i] == arr[i - 1]:
			l = i
	if l == -1 or l == b + 1:
		print(0)
	else:
		print(max(1, l - b - 2))
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	first_i = -1
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			first_i = i
			break
	if first_i == -1:
		print(0)
		continue
	last_i = first_i
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			last_i = i
	if last_i == first_i:
		print(0)
		continue
	if last_i == first_i + 1:
		print(1)
		continue
	print(last_i - first_i - 1)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (0, n - 1)
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			l += 1
		else:
			break
	for i in range(n - 1, 0, -1):
		if a[i] != a[i - 1]:
			r -= 1
		else:
			break
	nstochange = r - l - 1
	if nstochange <= 0:
		print(0)
	else:
		print(max(1, nstochange - 1))


import math

def get_list():
	return list(map(int, input().split()))

def get_int():
	return int(input())

def out(output):
	if output:
		print('YES')
	else:
		print('NO')
for i in range(get_int()):
	n = get_int()
	l = get_list()
	c = -1
	start = 0
	end = n
	for (a, item) in enumerate(l):
		if item == c:
			start = a
			break
		c = item
	c = -1
	for (a, item) in enumerate(list(reversed(l))):
		if item == c:
			end = a
			break
		c = item
	ans = n - end - start - 1
	if ans == 0:
		ans = 1
	if ans < 0:
		ans = 0
	print(ans)


def getMoves(nums):
	pairs = []
	for i in range(100, 0):
		for j in range(100, 0):
			j = i
	for i in range(len(nums) - 1):
		if nums[i] == nums[i + 1]:
			pairs.append([i, i + 1])
	if len(pairs) <= 1:
		return 0
	else:
		startA = pairs[0][0]
		startB = pairs[0][1]
		endA = pairs[-1][0]
		endB = pairs[-1][1]
		if endA - startB == 0:
			return 1
		return endA - startB
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	result = getMoves(nums)
	print(result)


def solve():
	n = int(input())
	l = 0
	c = 10 ** 9
	i = 0
	a = list(map(int, input().split()))
	while i < n - 1:
		if a[i] == a[i + 1]:
			c = min(c, i)
			l = max(l, i)
		i += 1
	if c == l or c == 10 ** 9:
		print(0)
		return
	if l - c < 3:
		print(1)
		return
	else:
		print(l - c - 1)
		return
for ii in range(int(input())):
	solve()


for tt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	op = 0
	f = False
	pair = []
	for i in range(n - 1):
		if a[i + 1] == a[i]:
			pair.append(i)
	if len(pair) <= 1:
		op = 0
	else:
		op = pair[-1] - pair[0]
		if op > 1:
			op = op - 1
	print(op)


from collections import defaultdict
from functools import lru_cache
import heapq
from locale import resetlocale
import sys
import random
import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s

def invr():
	return map(int, input().split())
T = inp()

def solve(nums):
	stack = []
	for i in range(len(nums) - 1):
		if nums[i] == nums[i + 1]:
			stack.append((nums[i], i))
	if len(stack) < 2:
		return 0
	return max(stack[-1][1] - stack[0][1] - 1, 1)
for _ in range(T):
	n = inp()
	nums = inlt()
	print(solve(nums))


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	n = len(l)
	start = -1
	while i < n - 1:
		if l[i] == l[i + 1]:
			start = i
			break
		i += 1
	if start == -1:
		print(0)
		continue
	end = -1
	i = start + 1
	while i < n - 1:
		if l[i] == l[i + 1]:
			end = i + 1
		i += 1
	if end == -1:
		print(0)
		continue
	si = end - start + 1
	if si <= 3:
		print(si - 2)
	else:
		print(si - 3)


x = int(input())
for i in range(x):
	n = int(input())
	s = input()
	arr = [int(l) for l in s.split(' ')]
	a = 0
	b = 0
	ans = 0
	for j in range(1, n):
		if arr[j] == arr[j - 1]:
			a = j
			break
	arr.reverse()
	for j in range(1, n):
		if arr[j] == arr[j - 1]:
			b = n - j
			break
	if b - a == 1:
		ans = 1
	elif b - a > 1:
		ans = b - a - 1
	print(ans)


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	c = 0
	first = 0
	last = 0
	c1 = 0
	for i in range(0, len(list1) - 1):
		if list1[i] == list1[i + 1]:
			if c == 0:
				first = i
				c = 1
			else:
				last = i
			c1 += 1
	if c == 0 or c1 == 1:
		print(0)
	else:
		diff = last - first - 1
		if diff == 0:
			print(1)
		else:
			print(diff)


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	start = None
	end = None
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			if start == None:
				start = i + 1
				end = i
			else:
				end = i
	if start == None:
		print(0)
	elif end - start < 0:
		print(0)
	elif start == end:
		print(1)
	else:
		print(end - start)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	(j, k) = (0, 0)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			count += 1
			if count == 1:
				j = i + 1
			else:
				k = i
	if count <= 1:
		print(0)
		continue
	if j == k:
		print(1)
	else:
		print(k - j)


for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	a = -1
	b = -1
	if N > 2:
		for i in range(N - 1):
			if A[i] == A[i + 1]:
				if b < 0:
					b = i
				a = i
	if a == b:
		print(0)
	else:
		print(max(1, a - b - 1))


t = int(input())
for _ in range(t):
	n = int(input())
	num = [int(x) for x in map(int, input().split(' ', n - 1))]
	l = []
	for i in range(n - 1):
		if num[i] == num[i + 1]:
			l.append(i)
	if len(l) <= 1:
		print(0)
	elif l[-1] - l[0] == 1:
		print(1)
	else:
		print(l[-1] - l[0] - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	first = 0
	last = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			first = i
			break
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			last = i + 1
	ans = last - first
	if ans == 2:
		print(1)
	elif ans > 2:
		print(ans - 2)
	else:
		print(0)


t = int(input())
for z in range(t):
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	r = []
	p = 0
	ans = 0
	if n <= 2:
		print(ans)
	else:
		for i in range(n - 1):
			if l[i] == l[i + 1]:
				r.append(i)
		if len(r) == 1 or len(r) == 0:
			ans = 0
		else:
			p = r[-1] - r[0]
			if p == 1:
				ans = 1
			else:
				ans = p - 1
		print(ans)


for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = []
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			ans.append(i)
	if len(ans) <= 1:
		print(0)
	elif max(ans) - min(ans) == 1:
		print(1)
	else:
		print(max(ans) - min(ans) - 1)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	l = -1
	m = -1
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			if m == -1:
				m = i
			l = i
	if l == m:
		print(0)
	else:
		print(max(1, l - m - 1))
	t = t - 1


import collections
import math
import sys

def main():
	n = int(input())
	a = list(map(int, input().split()))
	mn = 2 ** 100
	mx = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			mn = min(mn, i)
			mx = max(mx, i)
	if mn == mx or mn == 2 ** 100:
		print(0)
	elif mx - mn < 3:
		print(1)
	else:
		print(mx - mn - 1)
t = int(input())
while t > 0:
	main()
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	s1 = -1
	s2 = -1
	for j in range(n - 1):
		if l[j] == l[j + 1]:
			s += 1
	if s < 2:
		print(0)
		continue
	for j in range(n - 1):
		if l[j] == l[j + 1]:
			s1 = j
			break
	for j in range(n - 1, 0, -1):
		if l[j] == l[j - 1]:
			s2 = j
			break
	if s2 - s1 == 2:
		print(1)
		continue
	print(s2 - s1 - 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	last = -1
	pair = 0
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			last = i + 1
			pair += 1
	if last == -1 or pair == 1:
		print(0)
		continue
	for i in range(last):
		if l[i] == l[i + 1]:
			if last - i >= 3:
				print(last - i - 2)
			else:
				print(1)
			break


p = int(input())
for i in range(0, p):
	n = int(input())
	start = 0
	end = 0
	a = list(map(int, input().split()))
	for j in range(0, n - 1):
		if a[j] == a[j + 1]:
			start = j
			break
	for j in range(start, n - 1):
		if a[j] == a[j + 1]:
			end = j + 1
	x = end - start + 1
	if x > 3:
		print(x - 3)
	elif x == 3:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = -1
	l = -1
	for i in range(n):
		if i + 1 < n and a[i] == a[i + 1]:
			if f == -1:
				f = i + 1
			l = i
	if f == -1 or f > l:
		print(0)
	elif l == f:
		print(1)
	else:
		print(l - f)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a1 = []
	ct = 1
	x = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			ct += 1
			x = i
			break
		else:
			if ct != 1:
				a1.append(ct)
			ct = 1
	ct = 0
	y = 0
	for i in range(n - 1, 0, -1):
		if a[i] == a[i - 1]:
			ct += 1
			y = i
			break
		else:
			if ct != 1:
				a1.append(ct)
			ct = 1
	if x == 0 and y == 0:
		print(0)
	elif y - x + 1 == 2:
		print(0)
	elif y - x + 1 == 3 or y - x + 1 == 4:
		print(1)
	else:
		print(y - x + 1 - 3)


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	mn = n
	mx = 0
	for i in range(n - 1):
		if ls[i] == ls[i + 1]:
			mn = min(mn, i)
			mx = max(mx, i)
	c = mx - mn
	if c < 1:
		print(0)
	elif c < 3:
		print(1)
	else:
		print(c - 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	st = -1
	en = -1
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			if st == -1:
				st = i
			en = i
	if st == en:
		print(0)
	else:
		print(max(1, en - st - 1))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	lst = n - 2
	for i in range(n - 2, -1, -1):
		if arr[i] == arr[i + 1]:
			lst = i
			break
	cnt = 0
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			if i == lst:
				break
			elif i + 1 == lst:
				cnt = 1
				break
			else:
				cnt = lst - i - 1
				break
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	need = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			need += 1
		if need == 2:
			break
	if need == 0 or need == 1:
		print(0)
	else:
		op = 0
		s = 0
		e = 0
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				s = i
				break
		for i in range(n - 1, 0, -1):
			if a[i] == a[i - 1]:
				e = i
				break
		print(max(1, e - s - 2))


import sys

def unequal():
	n = int(input())
	arr = list(map(int, input().split()))
	mi = 2 ** 200
	ma = 0
	for j in range(n - 1):
		if arr[j] == arr[j + 1]:
			mi = min(mi, j)
			ma = max(ma, j)
	if mi == ma or mi == 2 ** 200:
		print(0)
	elif ma - mi < 3:
		print(1)
	else:
		print(ma - mi - 1)
t = int(input())
while t > 0:
	unequal()
	t = t - 1


from collections import defaultdict
import math as m

def get2int():
	p = input().split()
	return (int(p[0]), int(p[1]))

def get3int():
	p = input().split()
	return (int(p[0]), int(p[1]), int(p[2]))

def cinarr():
	arr = []
	for i in input().split():
		arr.append(int(i))
	return arr

def getParity(n):
	parity = 0
	while n:
		parity = ~parity
		n = n & n - 1
	return parity

def solve():
	n = int(input())
	s = cinarr()
	l = n
	r = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			l = min(l, i)
			r = max(r, i)
	if l == r or l == n:
		return 0
	elif r - l < 3:
		return 1
	else:
		return r - l - 1
for case in range(int(input())):
	print(solve())