Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible. 

Chef's video has N frames initially. The value of the i^{th} frame is A_{i}. Chef can do the following type of operation any number of times:
Choose an index i (1≤ i ≤ N) such that the value of the i^{th} frame is equal to the value of either of its neighbors and remove the i^{th} frame. 

Find the minimum number of frames Chef can achieve.

------ Input Format ------ 

- First line will contain T, the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N - the number of frames initially.
- The second line contains N space-separated integers, A_{1}, A_{2}, \ldots, A_{N} - the values of the frames.

------ Output Format ------ 

For each test case, output in a single line the minimum number of frames Chef can achieve.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
1
5
2
1 1
3
1 2 3
4
2 1 2 2

----- Sample Output 1 ------ 
1
1
3
3
----- explanation 1 ------ 
Test case $1$: There is only one frame with value $5$. Since there are no neighbors, Chef won't remove any frame and the minimum number of frames Chef can achieve is $1$.

Test case $2$: There are two frames where both frames have value $1$. Chef can remove the first frame as the value of the first frame is equal to that of the second frame. The remaining frames have values $[1]$. The minimum number of frames Chef can achieve is $1$.

Test case $3$: There are $3$ frames. All frames have distinct values. Thus, the minimum number of frames Chef can achieve is $3$.

Test case $4$: Chef can remove the fourth frame as the value of the fourth frame is equal to that of the third frame. The remaining frames have values $[2, 1, 2]$. Thus, the minimum number of frames Chef can achieve is $3$.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	n = int(input())
	video = list(map(int, input().split()))
	temp = []
	for j in range(0, n):
		if len(video) == 1:
			break
		elif j == 0:
			if video[j] == video[j + 1]:
				temp.append(video[j])
		elif j == n - 1:
			break
		elif video[j] == video[j + 1]:
			temp.append(video[j])
	print(len(video) - len(temp))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 1
	for j in range(n - 1):
		if a[j] != a[j + 1]:
			m += 1
	print(m)


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


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


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


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


T = int(input())
for i in range(T):
	N = int(input())
	n1 = list(map(int, input().split()))
	n2 = len(n1)
	for i in range(len(n1) - 1):
		if len(n1) == 1:
			print(1)
		elif n1[i] == n1[i + 1]:
			n2 -= 1
	print(n2)


def compress(l):
	res = []
	for i in range(len(l) - 1):
		if l[i] != l[i + 1]:
			res.append(l[i])
	if l[len(l) - 1] != l[-1]:
		res.append(l[-1])
	else:
		res.append(l[len(l) - 1])
	return res
n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	print(len(compress(l)))


T = int(input())
for i in range(T):
	m = 1
	N = int(input())
	f = list(map(int, input().split()))
	for i in range(len(f) - 1):
		if f[i] != f[i + 1]:
			m += 1
	print(m)


for i in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	f = 1
	for i in range(len(L) - 1):
		if L[i] != L[i + 1]:
			f += 1
	print(f)


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


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


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


T = int(input())
for i in range(T):
	N = int(input())
	frames = list(map(int, input().split()))
	temp = []
	for i in range(N - 1):
		if frames[i] == frames[i + 1]:
			pass
		else:
			temp.append(frames[i])
	print(len(temp) + 1)


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	c = 1
	for i in range(len(A) - 1):
		if A[i] != A[i + 1]:
			c += 1
	print(c)


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


for _ in range(int(input())):
	len_1 = int(input())
	list_1 = list(map(int, input().split(' ')))
	c = 1
	for i in range(0, len(list_1) - 1):
		if list_1[i] != list_1[i + 1]:
			c = c + 1
	print(c)


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


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


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	k = 0
	if n == 1:
		c = 1
	else:
		for i in range(n - 1):
			if l1[i] == l1[i + 1]:
				k += 1
	c = n - k
	print(c)


T = int(input())
for i in range(T):
	c = 1
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n - 1):
		if A[i] != A[i + 1]:
			c += 1
	print(c)


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


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	m = 1
	for j in range(0, N - 1):
		if a[j] != a[j + 1]:
			m = m + 1
	print(m)


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


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


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


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


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	li = []
	for i in range(len(A)):
		if li and li[-1] != A[i] or not li:
			li.append(A[i])
	print(len(li))


for i in range(int(input())):
	x = int(input())
	a = [int(x) for x in input().split()]
	flag = 0
	for i in range(x - 1):
		if x == 1:
			print(x)
			continue
		if a[i] == a[i + 1]:
			flag = flag + 1
	print(x - flag)


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


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	count = 1
	for i in range(N - 1):
		if A[i] != A[i + 1]:
			count += 1
	print(count)


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


T = int(input())
for i in range(T):
	N = int(input())
	a = list(input().split(' '))
	count = 0
	for j in range(N - 1):
		if a[j] == a[j + 1]:
			count += 1
	print(N - count)


for q in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	lis = []
	for i in range(len(arr)):
		if lis and lis[-1] != arr[i] or not lis:
			lis.append(arr[i])
	print(len(lis))


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	Alist = [1]
	for k in range(n - 1):
		if A[k] != A[k + 1]:
			Alist.append(A[k])
	print(len(Alist))


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


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	c = n
	for i in range(n - 1):
		j = i + 1
		if k[i] == k[j]:
			c -= 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	ele = list(map(int, input().split()))
	lst = []
	for i in range(len(ele)):
		if i != len(ele) - 1:
			if ele[i] != ele[i + 1]:
				lst.append(ele[i])
			else:
				continue
		else:
			lst.append(ele[i])
	print(len(lst))


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


T = int(input())
while T:
	c = 1
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(1, n):
		if arr[i - 1] != arr[i]:
			c += 1
	print(c)
	T -= 1


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


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


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	count = 1
	if n != 1:
		for i in range(n - 1):
			if l[i] != l[i + 1]:
				count += 1
	print(count)
	t -= 1