Tom is a string freak. He has got sequences of  n words to manipulate. If in a sequence, two same words come together then hell destroy each other. He wants to know the number of words left in the sequence after this pairwise destruction.
 
Example 1:
Input:
5
v[] = {"ab", "aa", "aa", "bcd", "ab"}
Output:
3
Explanation:
ab aa aa bcd ab
After the first iteration, we'll have: ab bcd ab
We can't further destroy more strings and
hence we stop and the result is 3. 
 
Example 2:
Input:
4
v[] = {"tom", "jerry", "jerry", "tom"}
Output:
0
Explanation:
tom jerry jerry tom
After the first iteration, we'll have: tom tom
After the second iteration: 'empty-array' 
Hence, the result is 0. 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function removeConsecutiveSame() which takes the array A[] and its size N as inputs and returns the number of words left per sequence.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 100
1 ≤ |S_{i}| ≤ 50

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:

class Solution:
    def removeAdj(self,v,n):
        # Your code goes here
        
    

Solutions:
class Solution:

	def removeAdj(self, v, n):
		st = []
		for i in v:
			if len(st) == 0:
				st.append(i)
			elif st[-1] == i:
				while st and st[-1] == i:
					st.pop()
			else:
				st.append(i)
		return len(st)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		for i in range(n):
			if len(stack) == 0:
				stack.append(v[i])
			elif stack[-1] == v[i] and stack:
				stack.pop()
				i = i + 1
			else:
				stack.append(v[i])
		return len(stack)


class Solution:

	def removeAdj(self, string, n):
		stack = []
		for i in range(n):
			if stack and string[i] == stack[-1]:
				stack.pop()
			else:
				stack.append(string[i])
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		l = []
		for i in range(n):
			if l == []:
				l.append(v[i])
			elif l[-1] == v[i]:
				l.pop()
			else:
				l.append(v[i])
		return len(l)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		for item in v:
			if stack and stack[-1] == item:
				stack.pop()
			else:
				stack.append(item)
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		for word in v:
			if len(stack) == 0:
				stack.append(word)
			elif word == stack[-1]:
				stack.pop()
			else:
				stack.append(word)
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		s = []
		for i in v:
			if s and s[-1] == i:
				s.pop()
			else:
				s.append(i)
		return len(s)


class Solution:

	def removeAdj(self, v, n):
		st = []
		for i in range(n):
			if not st:
				st.append(v[i])
			elif st and st[-1] == v[i]:
				st.pop()
			else:
				st.append(v[i])
		return len(st)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		cur = 1
		stack.append(v[0])
		while cur < n:
			if len(stack) > 0 and stack[-1] == v[cur]:
				stack.pop()
			else:
				stack.append(v[cur])
			cur += 1
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		sta = []
		s = n
		for i in range(n):
			if len(sta) != 0 and sta[-1] == v[i]:
				sta.pop()
				s -= 2
				continue
			sta.append(v[i])
		return s


class Solution:

	def removeAdj(self, v, n):
		stack = list()
		for i in v:
			if not stack or stack[-1] != i:
				stack.append(i)
			else:
				stack.pop()
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		i = 0
		while i < n:
			if not stack:
				stack.append(v[i])
			elif v[i] == stack[-1]:
				stack.pop()
			else:
				stack.append(v[i])
			i += 1
		return len(stack)


class Solution:

	def removeAdj(self, arr, n):
		stack = []
		for elm in arr:
			if len(stack) == 0 or stack[-1] != elm:
				stack.append(elm)
			else:
				stack.pop()
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		st = [-1]
		for i in v:
			top = st[-1]
			if top == i:
				st.pop()
			else:
				st.append(i)
		return len(st) - 1


class Solution:

	def removeAdj(self, v, n):
		self.arr = []
		for i in v:
			if len(self.arr) == 0:
				self.arr.append(i)
			elif self.arr[-1] == i:
				self.arr.pop()
			else:
				self.arr.append(i)
		r = len(self.arr)
		return r


from collections import deque

class Solution:

	def removeAdj(self, v, n):
		s = deque()
		for i in v:
			if len(s) != 0 and s[-1] == i:
				s.pop()
			else:
				s.append(i)
		return len(s)


class Solution:

	def removeAdj(self, arr, n):
		st = [arr[0]]
		for i in range(1, n):
			if st and arr[i] == st[-1]:
				st.pop()
			else:
				st.append(arr[i])
		return len(st)


class Solution:

	def removeAdj(self, v, n):
		re = []
		for item in v:
			if len(re) == 0:
				re.append(item)
			elif item == re[-1]:
				re.pop()
			else:
				re.append(item)
		return len(re)


class Solution:

	def removeAdj(self, v, n):
		l = []
		prev = []
		while True:
			c = len(v)
			prev = v
			l = []
			for i in range(c):
				if l == []:
					l.append(v[i])
				elif l[-1] != v[i]:
					l.append(v[i])
				else:
					l.pop()
			v = l.copy()
			if l == []:
				return 0
			elif prev == l:
				return len(l)


class Solution:

	def removeAdj(self, v, n):
		s = []
		add = True
		for i in v:
			add = True
			while s != [] and s[-1] == i:
				s.pop()
				add = False
			if add:
				s.append(i)
		return len(s)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		for ch in v:
			if len(stack) == 0:
				stack.append(ch)
			elif len(stack) > 0 and stack[-1] == ch:
				stack.pop()
			elif len(stack) > 0 and stack[-1] != ch:
				stack.append(ch)
		return len(stack)


class Solution:

	def removeAdj(self, arr, n):
		stck = []
		i = 0
		while i < len(arr):
			if len(stck) == 0:
				stck.append(arr[i])
				i += 1
			elif stck[-1] == arr[i]:
				stck.pop()
				i += 1
			else:
				stck.append(arr[i])
				i += 1
		return len(stck)


class Solution:

	def removeAdj(self, v, n):
		res = []
		for items in v:
			if len(res) == 0:
				res.append(items)
				continue
			elif items == res[-1]:
				res.pop()
			else:
				res.append(items)
		return len(res)


class Solution:

	def removeAdj(self, v, n):
		lst = []
		for x in v:
			if lst and lst[-1] == x:
				lst.pop()
			else:
				lst.append(x)
		return len(lst)


class Solution:

	def removeAdj(self, v, n):
		stk = []
		for e in v:
			if stk and stk[-1] == e:
				stk.pop()
			else:
				stk.append(e)
		return len(stk)


class Solution:

	def removeAdj(self, v, n):
		ans = ['0']
		for i in range(len(v)):
			if ans[len(ans) - 1] != v[i]:
				ans.append(v[i])
			else:
				ans.pop()
		return len(ans[1:])


class Solution:

	def removeAdj(self, v, n):
		s = v
		i = 0
		j = 0
		stack = []
		for i in range(n):
			if len(stack) == 0:
				stack.append(v[i])
				continue
			if stack[len(stack) - 1] == v[i]:
				stack.pop()
				continue
			stack.append(v[i])
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		stack = []
		for i in v:
			if len(stack) == 0:
				stack.append(i)
			else:
				x = stack[-1]
				if x == i:
					stack.pop()
				else:
					stack.append(i)
		return len(stack)


class Solution:

	def removeAdj(self, v, n):
		st = []
		for i in v:
			if len(st) == 0:
				st.append(i)
			elif i == st[-1]:
				st.pop()
			else:
				st.append(i)
		return len(st)
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		v = [x for x in input().split()]
		ob = Solution()
		print(ob.removeAdj(v, n))