You will receive 3 points for solving this problem.

Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.


-----Input-----

The input consists of a single line, containing a string s of length n (1 ≤ n ≤ 100). Each character of s will be from the set {'A', 'T', 'G', 'C'}.

This problem doesn't have subproblems. You will get 3 points for the correct submission.


-----Output-----

The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.


-----Examples-----
Input
GTTAAAG

Output
1

Input
AACCAACCAAAAC

Output
5



-----Note-----

In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.

Source: codeforces | Difficulty: MEDIUM
Tags: Amortized analysis

Implementation


Solutions:
def solve(s):
	result = 0
	i = 0
	while i < len(s):
		j = i
		while j < len(s) and s[i] == s[j]:
			j += 1
		if (j - i) % 2 == 0:
			result += 1
		i = j
	return result

def main():
	s = input()
	print(solve(s))
main()


from itertools import groupby
print(sum((1 for (k, g) in groupby(input()) if len(list(g)) % 2 == 0)))


s = input()
n = len(s)
ans = 0
k = 1
pre = s[0]
for i in range(1, n):
	if s[i] == pre:
		k += 1
	else:
		pre = s[i]
		if k % 2 == 0:
			ans += 1
		k = 1
if k != 0 and k % 2 == 0:
	ans += 1
print(ans)


n = input()
count = 1
ans = 0
j = 1
while j < len(n):
	if n[j] == n[j - 1]:
		while j < len(n) and n[j] == n[j - 1]:
			count += 1
			j += 1
		if count % 2 == 0:
			ans += 1
		count = 1
	else:
		j += 1
print(ans)


a = input()
n = len(a)
a = a + '0'
count = 1
ans = 0
for i in range(n):
	if a[i] == a[i + 1]:
		count += 1
	else:
		if count % 2 == 0:
			ans += 1
		count = 1
print(ans)


string = input()
s = string[0]
n = 0
values = []
for i in string:
	if i == s:
		n += 1
	else:
		values.append(n)
		n = 1
		s = i
values.append(n)
t = 0
for i in values:
	if i % 2 == 0:
		t += 1
print(t)


def count(sequence):
	result = 0
	current_length = 1
	for (i, x) in enumerate(sequence):
		if i == 0:
			continue
		if sequence[i - 1] == x:
			current_length += 1
			continue
		if current_length % 2 == 0:
			result += 1
		current_length = 1
	if current_length % 2 == 0:
		result += 1
	return result

def main():
	sequence = input()
	print(count(sequence))
main()


k = 1
p = r = 0
for x in input() + '0':
	if x != p:
		r += 1 - k % 2
		k = 0
		p = x
	k += 1
print(r)


s = input()
l = len(s)
ans = 0
i = 0
while i < l:
	j = i + 1
	while j < l and s[j] == s[i]:
		j += 1
	if j - i & 1 == 0:
		ans += 1
	i = j
print(ans)


str = input()
sum = 0
i = 0
j = 0
while i < len(str):
	pre = str[i]
	j = i
	while j < len(str) and str[j] == pre:
		j += 1
	if (j - i) % 2 == 0:
		sum += 1
	i = j
print(sum)


s = input()
Pred = ''
C = 0
D = 0
for i in s:
	if i == Pred:
		C += 1
	if i != Pred:
		if C % 2 == 0 and C != 0:
			D += 1
		C = 1
		Pred = i
if C % 2 == 0 and C != 0:
	D += 1
print(D)


def main():
	(a, cnt, res) = ('*', 1, 0)
	for b in input() + '*':
		if a != b:
			res += 1 - (cnt & 1)
			cnt = 1
			a = b
		else:
			cnt += 1
	print(res)

def __starting_point():
	main()
__starting_point()


import sys
string = str(sys.stdin.readline())
string = list(string)

def solution(string):
	count = 1
	answer = 0
	num = 0
	for i in string:
		if i == '\n':
			return print(answer)
		elif i == string[num + 1]:
			count += 1
		elif i != string[num + 1]:
			if count % 2 == 0 and count != 0:
				answer += 1
			count = 1
		num += 1
	return print(answer)
solution(string)


s = input()
num = 0
i = 0
while i < len(s):
	for j in range(i + 1, len(s) + 1):
		if j == len(s) or s[i] != s[j]:
			if (j - i) % 2 == 0:
				num += 1
			i = j - 1
			break
	i += 1
print(num)


n = input()
count = 1
c = 0
for i in range(len(n) - 1):
	if n[i] == n[i + 1]:
		count += 1
	elif count % 2 == 0:
		count = 1
		c += 1
	else:
		count = 1
if count % 2 == 0:
	count = 1
	c += 1
print(c)


s = input()
result = 0
sub = 0
last = s[0]
for x in s:
	if x == last:
		sub += 1
	else:
		if sub % 2 == 0:
			result += 1
		sub = 1
	last = x
if sub % 2 == 0:
	result += 1
print(result)


s = input()
p = s[0]
cnt = 1
ans = 0
for i in range(1, len(s)):
	if s[i] == p:
		cnt += 1
	else:
		if cnt % 2 == 0:
			ans += 1
		p = s[i]
		cnt = 1
if cnt % 2 == 0:
	ans += 1
print(ans)


strand = input()
add = 0
count = 1
for i in range(len(strand) - 1):
	if strand[i] == strand[i + 1]:
		count += 1
	elif strand[i] != strand[i + 1]:
		if count % 2 == 0:
			add += 1
		count = 1
	if i == len(strand) - 2:
		if count % 2 == 0:
			add += 1
print(add)


a = input()
a = ' '.join(a)
a = a.split()
suma = 0
contador = 0
for k in range(len(a)):
	if a[k] != '*':
		igual = a[k]
		contador = 0
		for r in range(k + 1, len(a)):
			if a[k] == a[r]:
				contador = contador + 1
				a[r] = '*'
			else:
				break
		if contador % 2 != 0:
			suma = suma + 1
print(suma)


r = input()
i = 0
outer_count = 0
while i < len(r):
	count = 0
	char = r[i]
	while r[i] == char:
		count += 1
		i += 1
		if i == len(r):
			break
	if count % 2 == 0:
		outer_count += 1
print(outer_count)


(X, Sum, Count) = (input() + '#', 1, 0)
for i in range(1, len(X)):
	if X[i] != X[i - 1]:
		if Sum % 2 == 0:
			Count += 1
		Sum = 1
	else:
		Sum += 1
print(Count)


a = []
s = input()
cnt = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		a.append(cnt)
		cnt = 1
a.append(cnt)
cnt = 0
for i in range(len(a)):
	if a[i] % 2 == 0:
		cnt += 1
print(cnt)


a = input()
cur = 1
ans = 0
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		cur += 1
	else:
		if not cur & 1:
			ans += 1
		cur = 1
if not cur & 1:
	ans += 1
print(ans)


s = input()
counter = 1
total = 0
for i in range(1, len(s), 1):
	if s[i] == s[i - 1]:
		counter += 1
	else:
		if counter % 2 == 0:
			total += 1
		counter = 1
if counter % 2 == 0:
	total += 1
print(total)


q = lambda : map(int, input().split())
x = input()
count = []
c = 1
if len(x) > 1:
	for (a, b) in zip(x, x[1:]):
		if a == b:
			c += 1
		else:
			count.append(c)
			c = 1
	if a == b:
		count.append(c)
	print(len([i for i in count if i % 2 == 0]))
else:
	print(0)


n = input()
x = 1
cnt = 0
for i in range(len(n) - 1):
	if n[i] == n[i + 1]:
		x += 1
	elif x % 2 == 0:
		cnt += 1
		x = 1
if x % 2 == 0:
	print(cnt + 1)
else:
	print(cnt)


import re
string = input()
result = sum((1 for a in re.compile('[A]+').findall(string) if len(a) % 2 == 0))
result += sum((1 for a in re.compile('[T]+').findall(string) if len(a) % 2 == 0))
result += sum((1 for a in re.compile('[G]+').findall(string) if len(a) % 2 == 0))
result += sum((1 for a in re.compile('[C]+').findall(string) if len(a) % 2 == 0))
print(result)


sequence = input()
changes = 0
even = True
last = sequence[0]
for i in range(0, len(sequence)):
	if last == sequence[i]:
		even = not even
	else:
		if even:
			changes += 1
		even = False
	last = sequence[i]
if even:
	changes += 1
print(changes)


s = input()
result = 0
last_ch = s[0]
last_ch_len = 1
for i in range(1, len(s)):
	if s[i] == last_ch:
		last_ch_len += 1
	else:
		if last_ch_len % 2 == 0:
			result += 1
		last_ch_len = 1
		last_ch = s[i]
if last_ch_len % 2 == 0:
	result += 1
print(result)


def main():
	line = input()
	array = []
	count = 0
	even = 0
	for char in line:
		if array == [] or array[-1] == char:
			array.append(char)
			count += 1
		else:
			array.append(char)
			if count % 2 == 0:
				even += 1
			count = 1
	if count % 2 == 0:
		even += 1
	print(even)
main()


def encode_protein():
	n = list(input())
	l = len(n)
	i = 0
	j = 0
	count = 0
	while i < l:
		while n[i] == n[j]:
			j += 1
			if j >= l:
				break
		if (j - i) % 2 == 0:
			count += 1
		i = j
	print(count)
encode_protein()


import math

def split(word):
	return [char for char in word]
fin = input()
gene = split(fin)
n = len(gene)
max = []
counter = 1
for i in range(1, n):
	if gene[i] == gene[i - 1]:
		counter += 1
	else:
		max.append(counter)
		counter = 1
max.append(counter)
answer = 0
for i in range(0, len(max)):
	if max[i] % 2 == 0:
		answer += 1
	else:
		answer += 0
print(answer)


h = input()
c = 1
l = h[0]
res = 0
for x in h[1:]:
	if x == l:
		c += 1
	else:
		if c % 2 == 0:
			res += 1
		l = x
		c = 1
if c % 2 == 0:
	res += 1
print(res)


string = input()
j = string[0]
count = 0
ans = 0
for i in range(len(string)):
	if string[i] == j:
		count = count + 1
	else:
		if count % 2 == 0:
			ans = ans + 1
		count = 1
		j = string[i]
if count % 2 == 0:
	ans = ans + 1
print(ans)


s = input()
ans = 0
count = 0
j = s[0]
for i in s:
	if i == j:
		count += 1
	else:
		if count % 2 == 0:
			ans += 1
		count = 1
		j = i
if count % 2 == 0:
	ans += 1
print(ans)


a = input() + ' '
total = 1
ans = 0
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		total += 1
	else:
		if total % 2 == 0:
			ans += 1
		total = 1
print(ans)


import math
import cmath
s = list(input())
n = len(s)
cnt = 1
ans = 0
for x in range(1, n):
	if s[x] == s[x - 1]:
		cnt += 1
	else:
		if cnt % 2 == 0:
			ans += 1
		cnt = 1
if cnt % 2 == 0:
	ans += 1
print(ans)


seq = input()
i = 0
j = 0
cnt = 0
ans = 0
while i < len(seq) and j < len(seq):
	if seq[i] != seq[j]:
		if cnt % 2 == 0:
			ans += 1
		i = j
		cnt = 0
	else:
		j += 1
		cnt += 1
if cnt % 2 == 0:
	ans += 1
print(ans)


str = input()
ans = 0
c = prev = 1
for i in str:
	if i == prev:
		c += 1
	else:
		prev = i
		if c % 2 == 0:
			ans += 1
		c = 1
if c % 2 == 0:
	ans += 1
print(ans)


dnk = input()
l = len(dnk)
para = 1
kolvo = 0
for i in range(l):
	a = dnk[i]
	if i != 0:
		b = dnk[i - 1]
	if i > 0:
		if a == b:
			para += 1
		if i == l - 1:
			if para % 2 == 0:
				kolvo += 1
				break
		if a != b:
			if para % 2 == 0:
				kolvo += 1
				para = 1
			else:
				para = 1
print(kolvo)


code = input()
curr = code[0]
curr_count = 1
add_count = 0
n = len(code)
for i in range(1, n):
	if code[i] == curr:
		curr_count += 1
		if i == n - 1:
			if curr_count % 2 == 0:
				add_count += 1
	else:
		curr = code[i]
		if curr_count % 2 == 0:
			add_count += 1
		curr_count = 1
print(add_count)


s = input()
mcount = 0
count = 1
for i in range(len(s) - 1):
	if s[i] == s[i + 1]:
		count += 1
	else:
		if count % 2 == 0:
			mcount += 1
		count = 1
if count % 2 == 0:
	mcount += 1
print(mcount)


def solve(s):
	n = len(s)
	arr = [val for val in s]
	ans = 0
	count = 1
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			count += 1
		else:
			if count % 2 == 0:
				ans += 1
			count = 1
	if count % 2 == 0:
		ans += 1
	return ans
s = input()
ans = solve(s)
print(ans)


import math
a = str(input())
b = ''
z = 0
n = 0
for i in range(len(a)):
	if b == '':
		z += 1
		b = a[i]
	elif b == a[i]:
		z += 1
	elif b != a[i]:
		if math.fmod(z, 2) == 0:
			n += 1
			z = 1
			b = a[i]
		else:
			z = 1
			b = a[i]
if math.fmod(z, 2) == 0:
	n += 1
print(n)


s = input()
cnts = []
cnt = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		cnts.append(cnt)
		cnt = 1
cnts.append(cnt)
print(sum([1 * int(cnts[i] % 2 == 0) for i in range(len(cnts))]))


s = input()
x = 1
c = s[0]
n = 0
for i in range(1, len(s)):
	if s[i] == c:
		x += 1
	else:
		if x % 2 == 0:
			n += 1
		x = 1
		c = s[i]
if x % 2 == 0:
	n += 1
print(n)


dna = input()
ans = 0
i = 0
while i < len(dna):
	j = i + 1
	while j < len(dna) and dna[j] == dna[j - 1]:
		j += 1
	if not j - i & 1:
		ans += 1
	i = j
print(ans)


import re
x = input()
l = [0 for i in range(len(x))]
(c, h) = (1, 0)
for i in range(len(x) - 1):
	(l, r) = (x[i], x[i + 1])
	if l is r:
		c += 1
	else:
		if c % 2 is 0:
			h += 1
		c = 1
if c % 2 is 0:
	h += 1
print(h)


def program(s):
	kol = 1
	koln = 0
	q = len(s) - 1
	i = 0
	while i != q:
		if s[i] == s[i + 1]:
			kol += 1
			i += 1
		elif kol % 2 == 0:
			koln += 1
			kol = 1
			i += 1
		else:
			kol = 1
			i += 1
	if kol % 2 == 0:
		koln += 1
	print(koln)
s = input()
program(s)


copy = code = input()
pieces = list()
i = 0
while len(code) != 0:
	piece = code[i]
	for j in range(len(code)):
		if code[j] in piece:
			piece += code[j]
		else:
			exit_index = j
			break
	try:
		code = code[exit_index:]
	except NameError:
		if len(code) % 2 == 0:
			print(1)
			exit()
		else:
			print(0)
			exit()
	pieces.append(len(piece) - 1)
even = sum((1 for _ in pieces if _ % 2 == 0))
print(even)


str = input()
temp = list()
formattedList = list()
temp.append(str[0])
i = 1
while i < len(str):
	previousChar = str[i - 1]
	presentChar = str[i]
	if presentChar == previousChar:
		temp.append(presentChar)
	else:
		formattedList.append(temp)
		temp = list()
		temp.append(presentChar)
	i += 1
if len(temp):
	formattedList.append(temp)
	temp = list()
numberOfAssert = 0
for item in formattedList:
	if len(item) % 2 == 0:
		numberOfAssert += 1
print(numberOfAssert)


s = input()
piece = ''
count = 0
for i in range(len(s) - 1):
	if s[i + 1] != s[i]:
		piece += s[i]
		if len(piece) % 2 == 0:
			count += 1
		piece = ''
	else:
		piece += s[i]
		if i == len(s) - 2 and s[len(s) - 2] == s[len(s) - 1]:
			piece += s[-1]
			if len(piece) % 2 == 0:
				count += 1
print(count)


(count, answer, prev) = (1, 0, '')
for letter in input():
	if prev == letter:
		count += 1
	elif count & 1 == 0:
		answer += 1
		count = 1
	prev = letter
if count & 1 == 0:
	answer += 1
print(answer)


import itertools
s = input()
z = [(x[0], len(list(x[1]))) for x in itertools.groupby(s)]
count = 0
for i in z:
	if i[1] % 2 == 0:
		count += 1
print(count)


def findMinInsertions(seq):
	seq += ' '
	insert = 0
	curr = ''
	for elt in seq:
		if curr == '':
			curr += elt
		elif elt == curr[0]:
			curr += elt
		else:
			if len(curr) % 2 == 0:
				insert += 1
			curr = elt
	return insert
seq = input()
print(findMinInsertions(seq))


s = input()
l = []
count = 0
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		count += 1
	else:
		l.append(count)
		count = 0
l.append(count)
ans = 0
for i in range(len(l)):
	if l[i] % 2 != 0:
		ans += 1
print(ans)


arr = input()
count = 0
insertion = 0
for i in range(1, len(arr)):
	if arr[i] == arr[i - 1]:
		count += 1
	else:
		if (count + 1) % 2 == 0:
			insertion += 1
		count = 0
if (count + 1) % 2 == 0:
	insertion += 1
print(insertion)


s = k = j = 0
for i in input():
	if i == j:
		k += 1
	else:
		s += k % 2
		(k, j) = (0, i)
print(s + k % 2)


y = input()
final = 0
i = 0
while i < len(y):
	if y[i] == 'A':
		flag = 0
		while i < len(y):
			if y[i] == 'A':
				flag += 1
			else:
				break
			i += 1
		if flag % 2 == 0:
			final = final + 1
	elif y[i] == 'T':
		flag = 0
		while i < len(y):
			if y[i] == 'T':
				flag += 1
			else:
				break
			i = i + 1
		if flag % 2 == 0:
			final = final + 1
	elif y[i] == 'G':
		flag = 0
		while i < len(y):
			if y[i] == 'G':
				flag += 1
			else:
				break
			i += 1
		if flag % 2 == 0:
			final = final + 1
	elif y[i] == 'C':
		flag = 0
		while i < len(y):
			if y[i] == 'C':
				flag += 1
			else:
				break
			i += 1
		if flag % 2 == 0:
			final = final + 1
print(final)


class CodeforcesTask391ASolution:

	def __init__(self):
		self.result = ''
		self.dna = ''

	def read_input(self):
		self.dna = input()

	def process_task(self):
		currc = ''
		count = 0
		inserts = 0
		for c in self.dna:
			if currc != c:
				currc = c
				if count:
					if not count % 2:
						inserts += 1
				count = 1
			else:
				count += 1
		if not count % 2:
			inserts += 1
		self.result = str(inserts)

	def get_result(self):
		return self.result
Solution = CodeforcesTask391ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


R = lambda : map(int, input().split())
s = input()
(cc, c) = (0, 0)
for r in range(len(s)):
	if r == 0 or s[r] == s[r - 1]:
		c += 1
	else:
		cc += c % 2 == 0
		c = 1
cc += c % 2 == 0
print(cc)


s = input()
nb = 1
n = 0
for i in range(len(s) - 1):
	if s[i] != s[i + 1] and nb % 2 == 0:
		n += 1
		nb = 1
	elif s[i] != s[i + 1]:
		nb = 1
	else:
		nb += 1
if nb % 2 == 0:
	print(n + 1)
else:
	print(n)


import sys
sys_in = input()

def counter(dna):
	count = 1
	even_count = 0
	previous = dna[0]
	dna = dna[1:]
	while dna != '':
		if dna[0] == previous:
			count += 1
		else:
			previous = dna[0]
			if count % 2 == 0:
				even_count += 1
			count = 1
		dna = dna[1:]
	if count % 2 == 0 and count != 0:
		even_count += 1
	return even_count
print(str(counter(sys_in)) + '\n')


import sys

def even(count):
	return count % 2 == 0

def genetic_engineering(word):
	consecutive_even_characters_count = 0
	char_count = 1
	for index in range(len(word) - 1):
		if word[index] == word[index + 1]:
			char_count += 1
		elif even(char_count):
			char_count = 1
			consecutive_even_characters_count += 1
		else:
			char_count = 1
	return consecutive_even_characters_count
for line in sys.stdin:
	print(genetic_engineering(line))


s = input() + '\x00'
c = 0
lp = 0
for (i, e) in enumerate(s):
	if s[lp] != e:
		if (i - lp) % 2 == 0:
			c += 1
		lp = i
print(c)


s = input()
f = {}
t = 1
for i in range(len(s)):
	if i > 0:
		if s[i] == s[i - 1]:
			f[t] += 1
		else:
			t += 1
			f[t] = 1
	else:
		f[t] = 1
count = 0
for x in f:
	if f[x] % 2 == 0:
		count += 1
print(count)