Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ seats in a row. You are given a string $S$ with length $N$; for each valid $i$, the $i$-th character of $S$ is '0' if the $i$-th seat is empty or '1' if there is someone sitting in that seat.

Two people are friends if they are sitting next to each other. Two friends are always part of the same group of friends. Can you find the total number of groups? 

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $S$. 

------  Output ------
For each test case, print a single line containing one integer ― the number of groups.

------  Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{5}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
4

000

010

101

01011011011110
----- Sample Output 1 ------ 
0

1

2

4
----- explanation 1 ------ 
Example case 1: Since all seats are empty, the number of groups is $0$.

Example case 2: Since only one seat is occupied, the number of groups is $1$.

Example case 3: Here, two seats are occupied, but since they are not adjacent, the people sitting on them belong to different groups.

Example case 4: Here, we have $4$ groups of friends with size $1$, $2$, $2$ and $4$ respectively. That is, first group is sitting at $2$nd seat, second group at $4$th and $5$th seat, third group at  $7$th and $8$th seat and fourth group at $10$th to $13$th seat.

Source: codechef | Difficulty: EASY
Tags: Complete search

Constructive algorithms

Ad-hoc


Solutions:
for _ in range(int(input())):
	s = input()
	p = s.split('0')
	print(len(p) - p.count(''))


for _ in range(int(input())):
	s = input()
	a = s.count('01')
	if s[0] == '1':
		print(a + 1)
	else:
		print(a)


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	if s[0] == '1':
		count += 1
	for i in range(1, len(s)):
		if s[i] == '1' and s[i - 1] == '0':
			count += 1
	print(count)


t = int(input())
for i in range(t):
	s = input()
	count = 0
	for i in range(len(s)):
		if s[i] == '1':
			if i + 1 == len(s):
				count += 1
			elif s[i + 1] == '0':
				count += 1
	print(count)


t = int(input())
for i in range(t):
	st = str(input())
	s = 0
	l = []
	for i in st:
		s = s + int(i)
		if i == '0':
			s = 0
		l.append(s)
	print(l.count(1))


t = int(input())
for i in range(t):
	s = input()
	count = 0
	current = 0
	l = len(s)
	for j in range(l):
		if s[j] == '1' and current == 0:
			current = 1
		if current == 1 and s[j] == '0':
			count = count + 1
			current = 0
	if current == 1:
		count += 1
	print(count)


for i in range(int(input())):
	a = input().split('0')
	print(len(a) - a.count(''))


for t in range(int(input())):
	s = input()
	if len(s) == s.count('0'):
		print(0)
	else:
		lis = list(s.split('0'))
		print(len(lis) - lis.count(''))


for _ in range(int(input())):
	s = input().split('0')
	cnt = 0
	for i in s:
		if i != '':
			cnt += 1
	print(cnt)


for i in range(int(input())):
	x = input()
	c = 0
	v = 0
	l = 0
	for i in x:
		l = l + 1
		if i == '1':
			v = 1
		if i == '0' and v == 1:
			c = c + 1
			v = 0
		if i == '1' and len(x) == l:
			c = c + 1
	print(c)


t = int(input())
for _ in range(t):
	s = input()
	cnt = 0
	prev = '0'
	for ch in s:
		if ch == '0':
			if prev == '1':
				cnt += 1
		prev = ch
	if prev == '1':
		cnt += 1
	print(cnt)


for _ in range(int(input())):
	s = input()
	som = s.count('1')
	start = s[0] == '1'
	grp = s.count('01')
	print(grp + start if som else 0)


import re
for i in range(int(input())):
	s = input()
	if s[0] == '1':
		renu = re.compile('1*0|1+1*')
	else:
		renu = re.compile('01*')
	r = renu.findall(s)
	if s.count('0') == 0:
		print(1)
	else:
		print(len(r) - r.count('0'))


import re
for i in range(int(input())):
	s = input()
	groups = re.findall('1+', s)
	print(len(groups))


import re
for i in range(int(input())):
	S = input()
	pattern = '1+'
	groups = re.findall(pattern, S)
	print(len(groups))


for i in range(int(input())):
	S = input()
	group_count = 0
	i = 0
	while i < len(S):
		if S[i] == '1':
			group_count += 1
			while i < len(S) and S[i] == '1':
				i += 1
		else:
			i += 1
	print(group_count)


for i in range(int(input())):
	s = input()
	ans = an = 0
	for j in s:
		if j == '1':
			an = 1
		else:
			ans += an
			an = 0
	ans += an
	print(ans)


for _ in range(int(input())):
	s = input()
	c = 0
	j = '0'
	for i in s:
		if i == j:
			continue
		c += 1
		j = i
	print((c + 1) // 2)


for i in range(int(input())):
	s = input()
	n = len(s)
	c = 0
	for j in range(0, n):
		if s[j] == '1':
			if j + 1 != n and s[j + 1] == '0':
				c = c + 1
	if s[n - 1] == '1':
		c = c + 1
	print(c)


for _ in range(int(input())):
	s = input()
	c = s.count('10')
	if s[-1] == '1':
		print(c + 1)
	else:
		print(c)


for i in range(int(input())):
	s = input()
	count = 0
	a = s.split('0')
	for j in a:
		if j != '':
			count += 1
	print(count)


for i in range(int(input())):
	a = input()
	count = 0
	if a[0] == '1':
		count += 1
	count += a.count('01')
	print(count)


t = int(input())
for i in range(t):
	cnt = 0
	s = input()
	n = len(s)
	for j in range(0, n):
		if s[j] == '1':
			if j + 1 != n and s[j + 1] == '0':
				cnt += 1
	if s[n - 1] == '1':
		cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	s = input()
	o = s.split('0')
	print(len(o) - o.count(''))


for i in range(int(input())):
	s = input()
	k = s.split('0')
	print(len(k) - k.count(''))


for _ in range(int(input())):
	n = input()
	l = n.split('0')
	flag = 0
	for i in l:
		if i != '':
			flag += 1
	print(flag)


for j in range(int(input())):
	str = input()
	str = str + '0'
	print(str.count('10'))


t = int(input())
for i in range(t):
	s = input()
	c = s.count('10')
	if s[-1] == '1':
		print(c + 1)
	else:
		print(c)


for _ in range(int(input())):
	l = input().split('0')
	c = 0
	for i in l:
		if i != '':
			c += 1
	print(c)


for tc in range(int(input())):
	s = input()
	count = 0
	arr = []
	for i in range(len(s)):
		if s[i] == '1':
			arr.append(i)
	for i in range(len(arr) - 1):
		if abs(arr[i + 1] - arr[i]) != 1:
			count += 1
	if len(arr) == 0:
		print(0)
	else:
		print(count + 1)


for _ in range(int(input())):
	sp = input()
	o = sp.split('0')
	print(len(o) - o.count(''))


def count_groups(S):
	n = len(S)
	count = 0
	for i in range(n):
		if i == 0 and S[i] == '1':
			count += 1
		elif i > 0 and S[i] == '1' and (S[i - 1] == '0'):
			count += 1
	return count
t = int(input().strip())
for _ in range(t):
	S = input().strip()
	result = count_groups(S)
	print(result)


for i in range(int(input())):
	c = 0
	s = input()
	a = s.split('0')
	for i in a:
		if i != '':
			c += 1
	print(c)


for _ in range(int(input())):
	x = input()
	count = 0
	flag = True
	for i in x:
		if i == '1':
			if flag:
				count += 1
				flag = False
		else:
			flag = True
	print(count)


for _ in range(int(input())):
	n = input()
	x = n.split('0')
	c = 0
	for i in x:
		if i != '':
			c += 1
	print(c)


for _ in range(int(input())):
	x = input()
	c = 0
	for i in range(len(x)):
		if x[i] == '1' and i == 0:
			c += 1
		elif x[i] == '1' and x[i - 1] == '0':
			c += 1
	print(c)


s = int(input())
for _ in range(s):
	l = input()
	o = l.split('0')
	print(len(o) - o.count(''))


n = int(input())
for i in range(n):
	a = input()
	count = 0
	for j in range(len(a)):
		if a[j] == '1' and j == 0:
			count = count + 1
		elif a[j] == '1' and a[j - 1] == '0':
			count = count + 1
	print(count)


T = int(input())
for _ in range(T):
	s = input()
	ones = s.split('0')
	print(len(ones) - ones.count(''))


t = int(input())
while t > 0:
	s = input()
	l = len(s)
	k = 0
	for i in range(l - 1):
		if s[i] == '1' and s[i + 1] == '0':
			k += 1
	if s[l - 1] == '1':
		print(k + 1)
	else:
		print(k)
	t = t - 1


T = int(input())
for _ in range(T):
	s = input()
	group = 0
	count = 0
	for i in s:
		if i == '0':
			if count > 0:
				group += 1
				count = 0
		else:
			count += 1
	if count > 0:
		group += 1
	print(group)


import re
for i in range(int(input())):
	s = input()
	l = re.findall('1+', s)
	if l != []:
		print(len(l))
	else:
		print('0')


import sys
for _ in range(int(sys.stdin.readline())):
	sys.stdout.write(str(sys.stdin.readline().replace('\n', '0').count('10')) + '\n')


import sys
for _ in range(int(sys.stdin.readline())):
	s = input().split('0')
	sys.stdout.write(str(len(s) - s.count('')) + '\n')


for i in range(int(input())):
	a = input()
	h = 0
	d = 0
	while h < len(a):
		if a[h] == '1':
			while a[h] == '1':
				h += 1
				if h == len(a):
					break
			d += 1
		else:
			h += 1
	print(d)


for _ in range(int(input())):
	s = input() + '0'
	print(s.count('10'))


for z in range(int(input())):
	s = input()
	group = 0
	count = 0
	for i in s:
		if i == '0':
			if count > 0:
				group += 1
				count = 0
		else:
			count += 1
	if count > 0:
		group += 1
	print(group)


T = int(input())

def group(idx, string):
	while idx < len(string):
		if string[idx] == '0':
			break
		else:
			idx = idx + 1
	return idx
while T > 0:
	S = str(input())
	i = 0
	cnt = 0
	while i < len(S):
		if S[i] == '1':
			i = group(i, S)
			cnt = cnt + 1
		else:
			i = i + 1
	print(cnt)
	T = T - 1


for _ in range(int(input())):
	t = input().split('0')
	a = 0
	for i in t:
		if i != '':
			a += 1
	print(a)


for _ in range(int(input())):
	s = input()
	c = 0
	if s[0] == '1':
		c += 1
	for i in range(1, len(s)):
		if s[i] == '1' and s[i - 1] == '0':
			c += 1
	print(c)


t = int(input())
for i in range(t):
	s = input()
	x = s.split('0')
	c = 0
	for i in x:
		if i != '0' and i != '':
			c = c + 1
	print(c)


for i in range(int(input())):
	s = input()
	group = s.split('0')
	x = 0
	for item in group:
		if item != '0' and item != '':
			x += 1
	print(x)


t = int(input())
while t > 0:
	x = input()
	count = 0
	zamn = 0
	for i in x:
		if i == '1':
			if zamn == 0:
				count += 1
				zamn = 1
		else:
			zamn = 0
	print(count)
	t -= 1


t = int(input())
while t:
	string = input()
	arr = string.split('0')
	cnt = 0
	for i in arr:
		if i != '':
			cnt += 1
	print(cnt)
	t -= 1