Read problems statements in Mandarin Chinese  and Russian. 

Chef is judging a game called "Broken telephone". There are total N players taking part in the game. They are all sitting in a line. In the start of the game, first player is given a secret message written on a sheet of paper. Then they keep sending the message by whispering it to the player sitting immediate right to one and so on until it reaches the last person. 

Finally, the message received by the last player is compared with the message said by first player. If these messages aren't equal, there is someone who has misheard the message or whispered it wrongly to the next player. If messages is equal, then the players win and receive a tasty chocolate. 

Note that first player receives the message on a sheet of paper, thus he cannot mishear it.

As Chef wants to be sure that every player has fulfilled his/ her role in the game, so he asks everyone to state their received messages after the end of the game. You are given an array A of N integers denoting messages received by each person.

Please help Chef to find the number of players that could mishear the message or whisper it wrongly.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. 
The first line of each test case contains a single integer N denoting the number of players
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the messages of players.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the number of players that could mishear the message or whisper it wrongly.

------ 
------ Constraints -----

$1 ≤ T ≤ 5$
$1 ≤ A_{i} ≤ 10^{9}$

Subtask 1: 40 points

$2 ≤ N ≤ 10^{3}$

Subtask 2: 60 points

$2 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------ 
3

7

1 1 1 3 3 3 2

5

1 3 1 1 1

4

5 5 5 5
----- Sample Output 1 ------ 
4

3

0
----- explanation 1 ------ 

Example 1: The 3-rd, 4-th, 6-th and 7-th player could mishear the message or whisper it wrongly.
Example 2: First 3 players could mishear the message or whisper it wrongly.

Difficulty: EASY
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	count = 0
	flag = False
	for i in range(0, N - 1):
		if A[i] != A[i + 1]:
			if flag:
				count += 1
			else:
				count += 2
				flag = True
		else:
			flag = False
	print(count)


for i in range(int(input())):
	n = int(input())
	array = [int(i) for i in input().split()]
	count = 0
	for j in range(0, n):
		if j > 0 and j < n - 1:
			if array[j] == array[j - 1] == array[j + 1]:
				count = count
			else:
				count = count + 1
		elif j == n - 1:
			if array[j] == array[j - 1]:
				count = count
			else:
				count = count + 1
		elif j == 0:
			if array[j] == array[j + 1]:
				count = count
			else:
				count = count + 1
	print(count)


for _ in range(int(input())):
	N = int(input())
	lst = list(map(int, input().split()))
	count = 0
	for i in range(1, N - 1):
		if lst[i] != lst[i + 1]:
			count += 1
		elif lst[i - 1] != lst[i + 1]:
			count += 1
	if lst[0] != lst[1]:
		count += 1
	if lst[N - 1] != lst[N - 2]:
		count += 1
	print(count)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	count = 0
	ser = 0
	sert = 0
	for j in range(1, len(b)):
		if b[j] != b[j - 1]:
			count += 2
			ser += 1
			if ser > 1:
				sert += 1
		else:
			ser = 0
	print(count - sert)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	A = [int(i) for i in input().split()]
	prev = A[0]
	count = 0
	flag = 0
	for i in range(1, N):
		if prev != A[i]:
			if flag == 0:
				count += 2
				flag = 1
			else:
				count += 1
		else:
			flag = 0
		prev = A[i]
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	g = list(map(int, input().split()))
	v = [-1] * n
	c = 0
	for i in range(n - 1):
		if g[i] != g[i + 1]:
			if v[i] == -1:
				c = c + 1
				v[i] = 0
			if v[i + 1] == -1:
				c = c + 1
				v[i + 1] = 0
	print(c)


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


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	li = []
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			li.append(i)
			li.append(i + 1)
	print(len(set(li)))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	s = set()
	for j in range(n - 1):
		if l[j] != l[j + 1]:
			s.add(j)
			s.add(j + 1)
	print(len(s))


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	count = 0
	for i in range(len(arr)):
		if i == 0:
			if arr[i] != arr[i + 1]:
				count += 1
		elif i == len(arr) - 1:
			if arr[i] != arr[i - 1]:
				count += 1
		elif arr[i] != arr[i - 1] or arr[i] != arr[i + 1]:
			count += 1
	print(count)


for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(count, ans) = (0, True)
	for i in range(n - 1):
		if ans == True and arr[i] != arr[i + 1]:
			count += 2
			ans = False
		elif ans == False and arr[i] != arr[i + 1]:
			count += 1
		elif ans == False and arr[i] == arr[i + 1]:
			ans = True
	print(count)


t = int(input())
for i in range(0, t, 1):
	n = int(input())
	l = list(map(int, input().split()))
	s = set()
	for j in range(0, n - 1, 1):
		if l[j] != l[j + 1]:
			if j not in s or j + 1 not in s:
				s.add(j)
				s.add(j + 1)
	print(len(s))


n = int(input())
for i in range(n):
	x = int(input())
	a = list(map(int, input().split()))
	r = 0
	c = 0
	for i in range(len(a) - 1):
		if a[i] != a[i + 1]:
			if r >= 1:
				c += 1
			else:
				c += 2
			r += 1
		else:
			r = 0
	print(c)


n = int(input())
for _ in range(n):
	k = int(input())
	lis = list(map(int, input().split()))
	dic = {}
	st = set()
	for i in range(k - 1):
		if lis[i] != lis[i + 1]:
			st.add(i)
			st.add(i + 1)
	print(len(st))


for k in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	faulty = set()
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			faulty.add(i)
			faulty.add(i + 1)
	print(len(faulty))


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = set()
	for j in range(len(b) - 1):
		if b[j] != b[j + 1]:
			c.add(j)
			c.add(j + 1)
	print(len(c))


for i in range(int(input())):
	number = int(input())
	arr = [int(i) for i in input().split()]
	c = 0
	for j in range(0, number):
		if j > 0 and j < number - 1:
			if arr[j] == arr[j - 1] == arr[j + 1]:
				c = c
			else:
				c = c + 1
		elif j == number - 1:
			if arr[j] == arr[j - 1]:
				c = c
			else:
				c = c + 1
		elif j == 0:
			if arr[j] == arr[j + 1]:
				c = c
			else:
				c = c + 1
	print(c)


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


vp = int(input())
for k in range(vp):
	t = int(input())
	c = list(map(int, input().split()))
	r = 0
	for i in range(t):
		if i == 0:
			if c[i] != c[i + 1]:
				r += 1
		elif i == t - 1:
			if c[i] != c[i - 1]:
				r += 1
		elif c[i] != c[i - 1] or c[i] != c[i + 1]:
			r += 1
	print(r)


tests = int(input())
for test in range(tests):
	number = int(input())
	string = list(map(int, input().split()))
	dic = {}
	previous = string[0]
	count = 0
	for i in range(1, number):
		if string[i] != previous:
			if dic.get(str(i - 1)):
				pass
			else:
				count += 1
				dic[str(i - 1)] = True
			if dic.get(str(i)):
				pass
			else:
				count += 1
				dic[str(i)] = True
		previous = string[i]
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(input().split())
	s = len(l)
	a1 = 0
	a2 = 0
	a3 = 0
	if l[0] != l[1]:
		a2 = a2 + 1
	else:
		a2 = a2
	if l[n - 2] != l[n - 1]:
		a3 = a3 + 1
	else:
		a3 = a3
	for i in range(s - 2):
		if i >= 0 and i < s - 2:
			if l[i] == l[i + 1] == l[i + 2]:
				a1 = a1
			else:
				a1 = a1 + 1
	print(a1 + a2 + a3)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(count, ans) = (0, True)
	for i in range(n - 1):
		if ans == True and l[i] != l[i + 1]:
			count += 2
			ans = False
		elif ans == False and l[i] != l[i + 1]:
			count += 1
		elif ans == False and l[i] == l[i + 1]:
			ans = True
	print(count)


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


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


test = int(input())
for i in range(test):
	N = int(input())
	S = map(int, input().split())
	lst = list(S)
	ans = []
	count = 0
	flag = False
	for i in range(0, N - 1):
		if lst[i] != lst[i + 1]:
			if flag:
				count += 1
			else:
				count += 2
				flag = True
		else:
			flag = False
	print(count)


for z in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(chk, count) = (0, 0)
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			if chk == 0:
				count += 2
			else:
				count += 1
			chk = 1
			continue
		chk = 0
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print(0)
	else:
		l = []
		for i in range(n - 1):
			if a[i] != a[i + 1]:
				l.append(i)
				l.append(i + 1)
		print(len(set(l)))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(count, flag) = (0, True)
	for i in range(len(A) - 1):
		if flag is True and A[i] != A[i + 1]:
			count += 2
			flag = False
		elif flag is False and A[i] != A[i + 1]:
			count += 1
		elif flag is False and A[i] == A[i + 1]:
			flag = True
	print(count)


def m(s):
	l = list(map(int, [*'0' * len(s)]))
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			l[i] = 1
			l[i + 1] = 1
	return l.count(1)
t = int(input())
for i in range(t):
	n = int(input())
	print(m(list(map(int, input().split()))))


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


for _ in range(int(input())):
	n = int(input())
	msgs = input().split(' ')
	mis = 0
	sai = 0
	for (i, j) in enumerate(msgs):
		if i != n - 1:
			if j != msgs[i + 1]:
				sai += 1
				continue
		if i != 0:
			if j != msgs[i - 1]:
				mis += 1
	print(mis + sai)


def check(a):
	count = 0
	for i in range(len(a)):
		if i == 0:
			if a[i] != a[i + 1]:
				count += 1
		elif i == len(a) - 1:
			if a[i] != a[i - 1]:
				count += 1
		elif a[i - 1] == a[i] == a[i + 1]:
			continue
		else:
			count += 1
	return count
cases = int(input())
for j in range(cases):
	size = int(input())
	arr = [int(x) for x in input().split()]
	print(check(arr))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	t = 1
	base = a[0]
	c = 0
	q = -50
	for i in range(1, len(a)):
		if base != a[i]:
			base = a[i]
			if i == q + 1:
				c += 1
			else:
				c += 2
			q = i
	print(c)


t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	lst = []
	for i in range(1, n):
		if a[i] != a[i - 1]:
			lst.append(i)
			lst.append(i - 1)
	d = set(lst)
	h = list(d)
	print(len(h))


t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in range(1, n):
		if a[i] != a[i - 1]:
			l.append(i)
			l.append(i - 1)
	d = set(l)
	c = list(d)
	print(len(c))


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


for _ in range(int(input())):
	n = int(input())
	arr = tuple(map(int, input().split()))
	s = set()
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			s.add(i)
			s.add(i + 1)
	print(len(s))


for t in range(int(input())):
	n_pl = int(input())
	n_msg = list(map(int, input().split()))
	n_msg_s = set()
	for i in range(n_pl - 1):
		if n_msg[i] != n_msg[i + 1]:
			n_msg_s.add(i)
			n_msg_s.add(i + 1)
	print(len(n_msg_s))


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i == 0:
			if arr[i] != arr[i + 1]:
				ans += 1
		elif i > 0 and i < n - 1:
			if arr[i] == arr[i + 1] == arr[i - 1]:
				ans = ans
			else:
				ans += 1
		elif i == n - 1:
			if arr[i] != arr[i - 1]:
				ans += 1
	print(ans)
	t -= 1