An array $a$ is good if for all pairs of adjacent elements, $a_i$ and $a_{i+1}$ ($1\le i \lt n$) are of different parity. Note that an array of size $1$ is trivially good.

You are given an array of size $n$.

In one operation you can select any pair of adjacent elements in which both elements are of the same parity, delete them, and insert their product in the same position.

Find the minimum number of operations to form a good array.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 100$).

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


-----Output-----

For each test case print an integer, the minimum number of operations required to form a good array.


-----Examples-----

Input
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3
Output
2
0
3


-----Note-----

Consider the first test case. Select the $2$-nd and the $3$-rd integers and apply the operation on them. The array changes from $[1, {7}, {11}, 2, 13]$ to $[1, {77}, 2, 13]$. Next, select the $1$-st and the $2$-nd integers, array changes from $[{1}, {77}, 2, 13]$ to $[{77}, 2, 13]$. Thus we require $2$ operations. It can be proved that this is the minimum number of operations.

In the second test case, the given array is already good. So we require $0$ operations.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
iter = int(input())
for _ in range(iter):
	n = int(input())
	a = list(map(int, input().split(' ')))
	op = 0
	for i in range(n - 1):
		if a[i] & 1 == a[i + 1] & 1:
			op += 1
	print(op)


def n_ops(a):
	op_count = 0
	for i in range(1, len(a)):
		if a[i] % 2 == a[i - 1] % 2:
			op_count += 1
	return op_count

def test_n_ops():
	assert n_ops([1, 1, 1, 2, 2, 3]) == 3
	assert n_ops([1]) == 0
	assert n_ops([1, 2]) == 0
	assert n_ops([1, 1]) == 1
	assert n_ops([1, 7, 11, 2, 13]) == 2
	assert n_ops([1, 2, 3, 4]) == 0

def main():
	n_cases = int(input().strip())
	for _ in range(n_cases):
		input()
		a = list(map(int, input().strip().split(' ')))
		print(n_ops(a))
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = map(int, input().split(' '))
	p = -1
	c = 0
	for x in a:
		if x % 2 == p:
			c += 1
		p = x % 2
	print(c)


import math
import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def print_min(miner):
	if miner == 9999999999999999:
		print(-1, end=' ')
	else:
		print(miner, end=' ')
for _ in range(inp()):
	n = inp()
	arr = inlt()
	prev = arr[0]
	total = 0
	for i in range(1, n):
		if arr[i] % 2 == prev % 2:
			total += 1
		prev = arr[i]
	print(total)


def main():
	i = int(input())
	for _ in range(i):
		n = int(input().strip('\r\n'))
		a = [int(x) for x in input().strip('\r\n').split()]
		cnt = 0
		rem = None
		for v in a:
			if v % 2 == rem:
				cnt += 1
			else:
				rem = v % 2
		print(cnt)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	answer = 0
	for i in range(1, n):
		if nums[i - 1] % 2 == nums[i] % 2:
			answer += 1
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	ans = 0
	for i in range(1, n):
		if L[i] % 2 == L[i - 1] % 2:
			ans += 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	ind = 0
	while ind < n - 1:
		if a[ind] % 2 == a[ind + 1] % 2:
			ans += 1
		ind += 1
	print(ans)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		count = 0
		ans = 0
		for i in range(1, n):
			if a[i] % 2 == a[i - 1] % 2:
				count += 1
			else:
				ans += count
				count = 0
		ans += count
		print(ans)
main()


n = int(input())
for _ in range(n):
	x = int(input())
	l = [int(i) for i in input().split()]
	count = 0
	for i in range(len(l) - 1):
		if l[i + 1] % 2 == 0 and l[i] % 2 == 0:
			count += 1
		elif l[i + 1] % 2 != 0 and l[i] % 2 != 0:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	answer = 0
	bounce = 1
	arr = [int(x) for x in input().split()]
	for i in range(1, n):
		if (arr[i] - arr[i - 1]) % 2 == 0:
			bounce += 1
		else:
			answer += bounce - 1
			bounce = 1
	answer += bounce - 1
	print(answer)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().rstrip().split()))
	s = 0
	for i in range(len(lst)):
		try:
			if lst[i] % 2 == lst[i + 1] % 2:
				s += 1
		except IndexError:
			break
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(len(a) - 1):
		if a[i] % 2 == 0 and a[i + 1] % 2 == 0 or (a[i] % 2 == 1 and a[i + 1] % 2 == 1):
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	operations = 0
	for i in range(1, n):
		if a[i] % 2 == a[i - 1] % 2:
			operations += 1
	print(operations)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	c = 0
	for i in range(n - 1):
		if A[i] % 2 == 0 and A[i + 1] % 2 == 0:
			c += 1
		if A[i] % 2 == 1 and A[i + 1] % 2 == 1:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	else:
		count = 0
		r = L[0] % 2
		for i in range(1, n):
			if L[i] % 2 == r:
				count += 1
			else:
				r = L[i] % 2
		print(count)


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	d = []
	for i in range(n):
		if z[i] % 2 == 0:
			d.append(0)
		else:
			d.append(1)
	ans = 0
	for i in range(1, n):
		if d[i - 1] == d[i]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	c = 0
	arro = arr[:-1]
	for (i, j) in enumerate(arro):
		if (arr[i + 1] + j) % 2 == 0:
			c += 1
	print(c)


import math
import bisect
from collections import defaultdict, Counter
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = 0
	e = 0
	o = 0
	for i in range(0, n):
		if a[i] % 2 == 0:
			e += 1
			if o > 0:
				ans += abs(o - 1)
			o = 0
		elif a[i] % 2 != 0:
			if e > 0:
				ans += abs(e - 1)
			e = 0
			o += 1
	if e > 0:
		ans += abs(e - 1)
	if o > 0:
		ans += abs(o - 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split(maxsplit=n)]
	ans = 0
	for i in range(0, n - 1):
		if a[i] % 2 == a[i + 1] % 2:
			ans += 1
	print(ans)


for i in range(int(input())):
	k = int(input())
	s = [int(i) for i in input().split()]
	count = 0
	if len(s) > 1:
		if s[0] % 2 == s[1] % 2:
			count += 1
		for i in range(1, k - 1):
			if s[i] % 2 == s[i + 1] % 2:
				count += 1
		print(count)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	z = input().split()
	k = 0
	for j in range(n - 1):
		if int(z[j]) % 2 == int(z[j + 1]) % 2:
			k += 1
	print(k)


from itertools import *
for s in [*open(0)][2::2]:
	print(sum((len([*g]) - 1 for (k, g) in groupby((int(x) % 2 for x in s.split())))))


def GoodArray(array):
	count = 0
	for i in range(len(array) - 1):
		if array[i] % 2 == array[i + 1] % 2:
			count += 1
	return count
t = int(input())
output = []
for i in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	output.append(GoodArray(array))
for answer in output:
	print(answer)


def Solve():
	n = int(input())
	v = list(map(int, input().split()))
	r = 0
	for i in range(len(v) - 1):
		if v[i] % 2 == 0 and v[i + 1] % 2 == 0 or (v[i] % 2 != 0 and v[i + 1] % 2 != 0):
			r += 1
	return r

def meow():
	t = int(input())
	while t != 0:
		print(Solve())
		t -= 1
meow()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	for i in range(n - 1):
		if l[i] % 2 == 0 and l[i + 1] % 2 == 0 or (l[i] % 2 == 1 and l[i + 1] % 2 == 1):
			cnt += 1
	print(cnt)


n = int(input())
for _ in range(n):
	l = int(input())
	tab = list(map(int, input().split()))
	sub_p = []
	temp = [tab[0]]
	for i in range(1, l):
		if tab[i - 1] % 2 == tab[i] % 2:
			temp.append(tab[i])
		else:
			sub_p.append(temp)
			temp = [tab[i]]
	sub_p.append(temp)
	res = 0
	for l_p in sub_p:
		res += len(l_p) - 1
	print(res)


def good_array(t, test_cases):
	for _ in range(t):
		n = test_cases[_][0]
		a = test_cases[_][1]
		count = 0
		for i in range(n - 1):
			if a[i] % 2 == a[i + 1] % 2:
				count += 1
		print(count)
t = int(input())
test_cases = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	test_cases.append((n, a))
good_array(t, test_cases)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	for i in range(1, n):
		if arr[i] % 2 != 0 and arr[i - 1] % 2 != 0 or (arr[i] % 2 == 0 and arr[i - 1] % 2 == 0):
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	count = sum([1 for (a, b) in zip(numbers, numbers[1:]) if a % 2 == b % 2])
	print(count)


tc = int(input())
for _ in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	coun = 0
	for i in range(1, n):
		if lst[i] % 2 == 1 and lst[i - 1] % 2 == 1:
			coun += 1
		elif lst[i] % 2 == 0 and lst[i - 1] % 2 == 0:
			coun += 1
	print(coun)


t = int(input())
A = []
for i in range(t):
	n = int(input())
	a = [int(p) for p in input().split()]
	A.append(a)
for i in range(t):
	arr = A[i]
	c = 0
	if arr[0] % 2 == 0:
		switch = True
		for j in range(1, len(arr)):
			if switch:
				if arr[j] % 2 == 0:
					c += 1
				else:
					switch = False
			elif arr[j] % 2 == 1:
				c += 1
			else:
				switch = True
	else:
		switch = False
		for j in range(1, len(arr)):
			if switch:
				if arr[j] % 2 == 0:
					c += 1
				else:
					switch = False
			elif arr[j] % 2 == 1:
				c += 1
			else:
				switch = True
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	n = len(a)
	ce = 0
	co = 0
	b = []
	f = a[0] % 2
	for i in range(n):
		if f == 0 and a[i] % 2 == 0:
			ce += 1
		elif f == 1 and a[i] % 2 == 0:
			b.append(co)
			co = 0
			ce = 1
			f = 0
		elif f == 1 and a[i] % 2 == 1:
			co += 1
		elif f == 0 and a[i] % 2 == 1:
			b.append(ce)
			ce = 0
			co = 1
			f = 1
	b.append(co)
	b.append(ce)
	r = 0
	for j in b:
		if j > 1:
			r += j - 1
	print(r)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from collections import Counter
from bisect import bisect_left as bl, bisect_right as br
import heapq
from itertools import permutations
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
test = int(input())
for _ in range(test):
	n = inp()
	a = seq()
	ans = 0
	for i in range(len(a) - 1):
		if a[i] % 2 == a[i + 1] % 2:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n - 1):
		if a[i] % 2 == 0 and a[i + 1] % 2 == 0:
			c += 1
		elif a[i] % 2 != 0 and a[i + 1] % 2 != 0:
			c += 1
	print(c)


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	n = int(input())
	L = [*map(int, input().split())]
	result = 0
	for i in range(len(L) - 1):
		f = L[i]
		s = L[i + 1]
		if (f ^ s) % 2 == 0:
			result += 1
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	(odd, even, ans) = (0, 0, 0)
	for e in a:
		if e % 2 == 0:
			even += 1
			odd = 0
		else:
			odd += 1
			even = 0
		if odd == 2:
			ans += 1
			odd = 1
		elif even == 2:
			ans += 1
			even = 1
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split(' ')))
	curr_par = arr[0] % 2
	if n == 1:
		print(0)
		continue
	switches = 0
	for i in range(1, n):
		new_par = arr[i] % 2
		if new_par != curr_par:
			curr_par = new_par
			switches += 1
	print(n - switches - 1)


t = int(input())
for _ in range(t):
	input()
	a = [int(x) for x in input().split()]
	count = 0
	for i in range(len(a) - 1):
		if a[i] % 2 == a[i + 1] % 2:
			count += 1
	print(count)


t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	op = 0
	s = 1
	for i in range(0, n - 1):
		if a[i] % 2 == a[i + 1] % 2:
			s += 1
		else:
			op += s - 1
			s = 1
	op += s - 1
	print(op)


def solveA():
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	consecs = 0
	currentPar = arr[0] % 2
	for x in arr[1:]:
		if x % 2 == currentPar:
			consecs += 1
		else:
			currentPar = x % 2
	print(consecs)
t = int(input())
for tc in range(t):
	solveA()


n = int(input())
for _ in range(n):
	t = int(input())
	a = list(map(int, input().split(' ')))
	i = 1
	res = 0
	while i < t:
		if a[i - 1] & 1 == a[i] & 1:
			res += 1
		i += 1
	print(res)


t = int(input())
while t > 0:
	n = int(input())
	inp = list(map(int, input().split()))
	op = 0
	for i in range(n):
		if inp[i] % 2 == 0:
			inp[i] = 0
		else:
			inp[i] = -1
	for i in range(n - 1):
		if inp[i] == inp[i + 1] == 0 or inp[i] == inp[i + 1] == -1:
			op += 1
	print(op)
	t -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = 0
	for j in range(0, n - 1):
		if (a[j] + a[j + 1]) % 2 == 0:
			p += 1
	print(p)


n = int(input())
for i in range(n):
	c = 0
	b = int(input())
	l = [int(i) for i in input().split()]
	for j in range(len(l) - 1):
		if l[j] % 2 == 0 and l[j + 1] % 2 == 0 or (l[j] % 2 != 0 and l[j + 1] % 2 != 0):
			l[j] = l[j] * l[j + 1]
			c += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n - 1):
		if arr[i] % 2 == arr[i + 1] % 2:
			count += 1
	print(count)


n = int(input())

def work(l):
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			return False
	return True
for _ in range(n):
	res = 0
	m = int(input())
	vals = list(map(lambda u: int(u) % 2, input().split()))
	for i in range(m - 1):
		if vals[i] == vals[i + 1]:
			res += 1
	print(res)


import math

def fun(x):
	ans = 0
	while x > 1:
		ans += x // 2
		x = x // 2 + x % 2
	return ans
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ln = 1
	p = a[0] % 2
	ans = 0
	for i in range(1, n):
		if a[i] % 2 == p:
			ln += 1
		else:
			ans += fun(ln)
			ln = 1
			p = a[i] % 2
	ans += fun(ln)
	print(ans)


t = int(input())
for f in range(t):
	gta = int(input())
	b_b = list(map(int, input().split()))
	it = 0
	for i in range(gta - 1):
		if b_b[i] % 2 == 0 and b_b[i + 1] % 2 == 0 or (b_b[i] % 2 == 1 and b_b[i + 1] % 2 == 1):
			it = it + 1
	print(it)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		if a[i] % 2 == 0 and a[i + 1] % 2 == 0 or (a[i] % 2 == 1 and a[i + 1] % 2 == 1):
			ans += 1
	print(ans)


t = int(input())
for j in range(t):
	p = int(input())
	l = list(map(int, input().split()))
	count = 0
	for i in range(len(l) - 1):
		if l[i] % 2 == 0 and l[i + 1] % 2 == 0 or (l[i] % 2 != 0 and l[i + 1] % 2 != 0):
			count += 1
	print(count)


N = int(input())

def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	res = 0
	for i in range(1, n):
		if A[i] % 2 == A[i - 1] % 2:
			res += 1
	print(res)
for i in range(N):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	count = 0
	for j in range(n - 1):
		if a[j] % 2 == a[j + 1] % 2:
			count += 1
	print(count)


n = int(input())
for i in range(n):
	m = int(input())
	number = input()
	array = number.split()
	initial = -1
	count = 0
	for j in range(m):
		parity = int(array[j]) % 2
		if j == 0:
			initial = parity
		elif parity == initial:
			count += 1
		else:
			initial = parity
	print(count)


test = int(input().strip())
for _ in range(test):
	n = int(input().strip())
	ar = list(map(int, input().strip().split()))
	c = 0
	for i in range(n - 1):
		if n <= 0:
			c = 0
		if ar[i] % 2 == 0 and ar[i + 1] % 2 == 0 or (ar[i] % 2 == 1 and ar[i + 1] % 2 == 1):
			c += 1
	print(c)


def calc_op(a, n):
	chpos = []
	ch = a[0] % 2
	count_ch = 0
	for i in range(1, n):
		ch_new = a[i] % 2
		if ch_new == ch:
			count_ch += 1
		else:
			chpos.append(count_ch)
			count_ch = 0
			ch = ch_new
	chpos.append(count_ch)
	return sum(chpos)
t = int(input())
for t in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = calc_op(a, n)
	print(res)


cases = int(input())
for j in range(cases):
	n = int(input())
	counter = 0
	a = [int(x) for x in input().split()]
	i = 0
	for i in range(n - 1):
		if a[i] % 2 ^ a[i + 1] % 2 == 1:
			counter += 1
	print(n - counter - 1)


def good_array(l):
	n = len(l)
	operations = 0
	for i in range(n - 1):
		if l[i] % 2 and l[i + 1] % 2 or (l[i] % 2 == 0 and l[i + 1] % 2 == 0):
			operations += 1
	return operations
n = int(input())
for i in range(n):
	size = int(input())
	arr = list(map(int, input().split()))
	print(good_array(arr))


t = int(input())
result = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	curr = 0
	if n != 1:
		(i, j) = (0, 1)
		while j < n:
			if a[i] % 2 == 0 and a[j] % 2 == 0 or (a[i] % 2 != 0 and a[j] % 2 != 0):
				curr += 1
			i += 1
			j += 1
	result.append(curr)
for num in result:
	print(num)


t = int(input(''))

def test(s):
	c = 0
	for k in range(len(s) - 1):
		if int(s[k]) % 2 == 0 and int(s[k + 1]) % 2 == 0:
			c += 1
		elif int(s[k]) % 2 != 0 and int(s[k + 1]) % 2 != 0:
			c += 1
	return c
l = []
for i in range(t):
	n = int(input(''))
	s = input('').split(' ')
	l.append(test(s))
for j in range(len(l)):
	print(l[j])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n - 1):
		if n == 1:
			print(0)
			break
		if l[i] & 1 == l[i + 1] & 1:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	tf = l[0] % 2
	count = 0
	for i in range(n):
		if l[i] % 2 == tf:
			count += 1
		else:
			tf = (tf + 1) % 2
	print(count - 1)


def solve(n, a):
	cnt = 0
	for i in range(1, n):
		if a[i - 1] % 2 == a[i] % 2:
			cnt += 1
	return cnt
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


import heapq
import math
eps = 10 ** (-9)
from math import ceil, log

def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	res = 0
	for i in range(n - 1):
		if a[i] % 2 == a[i + 1] % 2:
			res += 1
	print(res)
	return
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for j in range(1, n):
		if a[j - 1] % 2 == 0 and a[j] % 2 == 0:
			x += 1
		elif a[j - 1] % 2 == 1 and a[j] % 2 == 1:
			x += 1
	print(x)


def min_operations(arr):
	count = 0
	for i in range(1, len(arr)):
		if arr[i] % 2 == arr[i - 1] % 2:
			count += 1
	return count
t = int(input())
tests = []
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	tests.append([n, arr])
for i in range(t):
	(n, arr) = tests[i]
	print(min_operations(arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ff = 0
	x = a[0]
	c = 0
	for i in range(1, n):
		if x % 2 == a[i] % 2:
			c += 1
		else:
			x = a[i]
	print(c)


def process_array(array, number_of_elements):
	count_of_operations = 0
	for i in range(number_of_elements - 1):
		if array[i] % 2 == array[i + 1] % 2:
			count_of_operations += 1
	return count_of_operations

def process_inputs_a():
	number_of_inputs = int(input())
	for i in range(number_of_inputs):
		number_of_elements = int(input())
		array = [int(x) for x in input().split()]
		print(process_array(array, number_of_elements))

def main():
	process_inputs_a()
main()


import collections
import math
import itertools
import operator

def ii():
	return int(input())

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

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

def findValue(numbers, low, high, value):
	rez = -1
	while low <= high:
		middle = low + (high - low) // 2
		if numbers[middle] >= value:
			rez = middle
			high = middle - 1
		else:
			low = middle + 1
	return rez
for _ in range(ii()):
	n = ii()
	a = li()
	ans = 0
	for i in range(n - 1):
		if a[i] & 1 and a[i + 1] & 1 or (a[i] % 2 == 0 and a[i + 1] % 2 == 0):
			ans += 1
	print(ans)


nope = int(input())
for i in range(nope):
	hehe = int(input())
	now = list(map(int, input().split()))
	res = 0
	for i in range(hehe - 1):
		if now[i] % 2 == 0 and now[i + 1] % 2 == 0 or (now[i] % 2 == 1 and now[i + 1] % 2 == 1):
			res += 1
	print(res)


for i in range(int(input())):
	n = int(input())
	x = [int(i) for i in input().split()]
	c = 0
	for i in range(n - 1):
		if x[i] % 2 != 0 and x[i + 1] % 2 != 0 or (x[i] % 2 == 0 and x[i + 1] % 2 == 0):
			c += 1
	print(c)


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum((1 & ~(x ^ y) for (x, y) in zip(a, a[1:]))))


def print_non_same_partial(n, arr):
	count = 0
	for i in range(1, n):
		if arr[i - 1] % 2 == arr[i] % 2:
			count += 1
	print(count)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = [int(num) for num in input().split()]
		print_non_same_partial(n, arr)
main()


for i in range(int(input())):
	n = int(input())
	v = []
	x = list(map(int, input().split()))
	b = 0
	for i in range(n):
		v.append(x[i] % 2)
	i = 0
	while i < n - 1:
		if v[i] == v[i + 1]:
			b += 1
			del v[i]
			n -= 1
		else:
			i += 1
	print(b)


def problem_a(nums):
	total = 0
	for i in range(len(nums) - 1):
		if nums[i] % 2 == nums[i + 1] % 2:
			total += 1
	return total
num_problems = int(input().strip())
for i in range(num_problems):
	num_p = int(input().strip())
	nums = list(map(int, input().strip().split()))
	r = problem_a(nums)
	print(r)


def min_ops(arr):
	n = len(arr)
	ops = 0
	for i in range(1, n):
		if arr[i] % 2 == arr[i - 1] % 2:
			ops += 1
	return ops
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(min_ops(arr))


def solve(n, l):
	even_c = 0
	odd_c = 0
	res = 0
	for i in l:
		if i % 2 == 0:
			if odd_c != 0:
				res += odd_c - 1
				odd_c = 0
			if odd_c == 0:
				even_c += 1
			else:
				even_c = 0
		else:
			if even_c != 0:
				res += even_c - 1
				even_c = 0
			if even_c == 0:
				odd_c += 1
			else:
				odd_c = 0
	if odd_c != 0:
		res += odd_c - 1
	if even_c != 0:
		res += even_c - 1
	return res
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(n, l))


m = int(input())
for k in range(m):
	n = int(input())
	ls = list(map(int, input().split()))
	cnt = ls[0] % 2
	ans = 0
	for i in range(1, n):
		if ls[i] % 2 == cnt:
			ans += 1
		cnt = ls[i] % 2
	print(ans)


import sys
import os
name_input_file = 'input.txt'
name_output_file = 'output.txt'
if os.path.exists('local.json'):
	name_input_file = sys.argv[0].split('\\')[-1].split('.')[0] + '.txt'
	name_output_file = sys.argv[0].split('\\')[-1].split('.')[0] + '_out.txt'

def read_data():
	return sys.stdin.readline().strip()

def main():
	c = int(read_data())
	for _ in range(c):
		n = int(read_data())
		res = 0
		data = []
		for i in read_data().split(' '):
			num = int(i)
			data.append(num)
		prev = data[0]
		for i in range(1, n):
			if data[i] % 2 == prev % 2:
				res += 1
			else:
				prev = data[i]
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	ans = 0
	for i in range(n - 1):
		if (a[i] + a[i + 1]) % 2 == 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [0 if int(x) % 2 == 0 else 1 for x in input().split(' ')]
	num = arr[0] ^ 2
	ans = 0
	prev = -1
	for i in arr:
		if i == prev:
			ans += 1
		prev = i
	print(ans)


def solve(numbers):
	res = 0
	for (left, right) in zip(numbers, numbers[1:]):
		same_parity = left % 2 == right % 2 == 0 or left % 2 == right % 2 == 1
		if same_parity:
			res += 1
	return res
n = int(input())
for _ in range(n):
	k = int(input())
	lst = list(map(int, input().split()))
	res = solve(lst)
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(ans, e, o) = (0, 0, 0)
	i = 0
	while i < n:
		if l[i] % 2 == 0:
			while i < n and l[i] % 2 == 0:
				i += 1
				e += 1
			ans += e - 1
			e = 0
		else:
			while i < n and l[i] % 2 == 1:
				i += 1
				o += 1
			ans += o - 1
			o = 0
	print(ans)


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


n = int(input())
a = [0 for i in range(n)]
for i in range(n):
	cnt = 0
	list_len = int(input())
	li = list(map(int, input().split()))
	for k in range(list_len - 1):
		if (li[k] + li[k + 1]) % 2 == 0:
			cnt += 1
	a[i] = cnt
for i in range(n):
	print(a[i])


import math
t = int(input())
for _ in range(t):
	su = 0
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	for i in range(n - 1):
		if l[i] % 2 == l[i + 1] % 2:
			c += 1
	print(c)


cases = int(input())
for c in range(cases):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	ans = 0
	curr_par = 0
	for i in range(1, n):
		if arr[i] % 2 == arr[i - 1] % 2:
			curr_par += 1
		else:
			ans += curr_par
			curr_par = 0
	ans += curr_par
	print(ans)