Given a string contains 'E' and 'O', 'E' represents a number is even and 'O' represents a number is odd. To make an element even, you can add 1 to any odd element of the array. Also, when any element of the array is converted to even, any neighboring element which is odd, can also be made even without adding 1. The task is to find the minimum number of additions required to make all the elements even. 
Example 1:
Input: S = "EOOE"
Output: 1
Explanation: Add 1 to 2nd element, 
it's neighbour 3rd element will 
convert into even. 
Example 1:
Input: S = "EOOOOE"
Output: 1
Explanation: Add 1 to 2nd element, 
it's neighbour 3rd element will 
convert into even. Then 4th and 
5th elements too
Your Task:
You don't need to read input or print anything. Your task is to complete the function convertToEven() which takes a string as inputs and returns the minimum number of additions required. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= |S| < 10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:
    def convertToEven(self, s):
        # code here


Solutions:
class Solution:

	def convertToEven(self, s):
		c = 0
		t = 0
		for i in range(len(s)):
			if s[i] == 'E':
				if t:
					c += 1
					t = 0
			else:
				t += 1
		if t:
			c += 1
		return c


class Solution:

	def convertToEven(self, s):
		i = 0
		count = 0
		while i < len(s):
			if s[i] == 'O':
				count += 1
				while i < len(s) and s[i] == 'O':
					i += 1
			i += 1
		return count


class Solution:

	def convertToEven(self, s):
		l = []
		c = 0
		for i in range(len(s)):
			if s[i] == 'O':
				if len(l) == 0:
					c += 1
				l.append('O')
			if s[i] == 'E':
				while len(l) != 0:
					l.pop()
		return c


class Solution:

	def convertToEven(self, s):
		c = 0
		for i in range(len(s)):
			if i == 0 and s[i] == 'O':
				c += 1
			elif s[i] == 'O' and s[i - 1] == 'E':
				c += 1
		return c


class Solution:

	def convertToEven(self, s):
		x = ''
		lst = []
		c = 0
		for i in s:
			if i == 'O':
				if x == 'O':
					c += 1
				else:
					x = 'O'
					c = 1
			elif c > 0:
				lst.append(c)
				c = 0
		if c > 0:
			lst.append(c)
		return len(lst)


class Solution:

	def convertToEven(self, s):
		x = []
		count = 0
		current = None
		for i in s:
			if i == 'O':
				if current == 'O':
					count += 1
				else:
					current = 'O'
					count = 1
			elif count > 0:
				x.append(count)
				count = 0
		if count > 0:
			x.append(count)
		return len(x)


class Solution:

	def convertToEven(self, s):
		n = 0
		if s[0] != 'E':
			n += 1
		for i in range(len(s) - 1):
			if s[i] == 'E':
				if s[i + 1] == 'O':
					n += 1
		return n


class Solution:

	def convertToEven(self, s):
		res = 0
		z = 0
		for i in s:
			if i == 'O' and z == 0:
				z = 1
				res += 1
			if i == 'E' and z == 1:
				z = 0
		return res


class Solution:

	def convertToEven(self, s):
		l = []
		l[:0] = s
		count = 0
		i = 0
		while i < len(l):
			if l[i] == 'O':
				count += 1
				j = i + 1
				while j < len(l):
					if l[j] == 'O':
						j += 1
					else:
						break
				i = j
			else:
				i += 1
		return count


class Solution:

	def convertToEven(self, s):
		patchesOfO = 0
		oSeen = False
		for i in range(len(s)):
			if s[i] == 'O':
				if not oSeen:
					oSeen = True
			if s[i] == 'E':
				if oSeen:
					patchesOfO += 1
					oSeen = False
		if oSeen:
			patchesOfO += 1
		return patchesOfO


class Solution:

	def convertToEven(self, s):
		count = 0
		s = s.split('E')
		g = list(filter(lambda a: a != '', s))
		return len(g)


class Solution:

	def convertToEven(self, s):
		st = []
		f = 0
		c = 0
		for e in s:
			while len(st) != 0 and st[-1] != 'E' and (e == 'E'):
				st.pop()
				if f == 0:
					c += 1
					f = 1
			f = 0
			st.append(e)
		if st[-1] == 'O':
			c += 1
		return c


class Solution:

	def convertToEven(self, s):
		l = len(s)
		count = 0
		i = 0
		if s[0] == 'O':
			count = count + 1
		while i < l - 1:
			if s[i] == 'E' and s[i + 1] == 'O':
				count = count + 1
				i = i + 2
			else:
				i = i + 1
		return count


class Solution:

	def convertToEven(self, s):
		o = 0
		for i in range(len(s) - 1):
			if s[i] != s[i + 1] and s[i] == 'O':
				o += 1
		if s[len(s) - 1] == 'O':
			o += 1
		return o


class Solution:

	def convertToEven(self, s):
		ls = s.split('E')
		ct = 0
		for x in ls:
			if len(x) != 0:
				ct += 1
		return ct


class Solution:

	def convertToEven(self, s):
		i = 0
		j = 0
		if s[i] == 'O':
			j += 1
		while i < len(s) - 1:
			if s[i] == 'E' and s[i + 1] == 'O':
				j += 1
			i += 1
		return j
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.convertToEven(s)
		print(ans)


class Solution:

	def convertToEven(self, s):
		st = []
		cnt = 0
		for i in range(len(s)):
			if s[i] == 'O':
				if len(st) == 0:
					cnt += 1
				st.append('O')
			if s[i] == 'E':
				while len(st) != 0:
					st.pop()
		return cnt


class Solution:

	def convertToEven(self, s):
		i = 0
		n = len(s)
		ans = 0
		while i < n:
			if i < n and s[i] == 'O':
				ans += 1
				while i < n and s[i] == 'O':
					i += 1
			else:
				while i < n and s[i] == 'E':
					i += 1
		return ans


class Solution:

	def convertToEven(self, s):
		l = list(s.split('E'))
		ans = len(l) - l.count('')
		return ans


class Solution:

	def convertToEven(self, s):
		last_ele = 'E'
		count = 0
		for i in s:
			if i == 'E':
				if last_ele == 'o':
					count += 1
					last_ele = 'E'
			elif last_ele == 'E':
				last_ele = 'o'
		if last_ele == 'o':
			count += 1
		return count


class Solution:

	def convertToEven(self, s):
		lst = s.split('E')
		count = 0
		for i in lst:
			if i != '':
				count += 1
		return count


class Solution:

	def convertToEven(self, s):
		c = 1
		a = []
		if 'O' not in s:
			return 0
		if 'E' not in s:
			return 1
		else:
			for i in range(len(s)):
				if s[i] == 'O':
					a.append(i)
			for i in range(len(a) - 1):
				if a[i + 1] - a[i] != 1:
					c = c + 1
			return c