nice-arches-1

Nikki's latest work is writing an story of letters. However, she finds writing story so boring that, after working for three hours, she realized that all she has written are M long words consisting entirely of letters A and B. Having accepted that she will never finish the story in time, poor Nikki has decided to at least have some fun with it by counting bubbly words.

Now Nikki is connecting pairs of identical letters (A with A, B with B) by drawing arches above the word. A given word is bubbly if each letter can be connected to exactly one other letter in such a way that no two arches intersect. So here is your task. Help Nikki count how many words are bubbly.

Input :

The first line of input contains the positive integer M , the number of words written down by Nikki. Each of the following M lines contains a single word consisting of letters A and B, with length between 2 and 10^5, inclusive. The sum of lengths of all words doesn't exceed 10^6.

Output :

The first and only line of output must contain the number of bubbly words.

Constraints:

1 ≤ M ≤ 100

SAMPLE INPUT
3
ABAB
AABB
ABBA

SAMPLE OUTPUT
2

Explanation

ABAB - It is not bubbly as A(indexed 1) will connect to A(indexed 3) by an arch and when we try to connect B(indexed 2) with B(indexed 4) by an arch then it will intersect with the arch b/w A and A.
AABB - It is bubbly as arch b/w A and A will not intersect with the arch b/w B and B.
ABBA - It is also bubbly as  arches will not intersect. we can draw arches b/w A and A above the arch b/w B and B.

Difficulty: MEDIUM
Tags: Fundamentals

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = int(input())
ans  = 0
for i in range(n):
	s = []
	w = input()
	for c in w:
		if c == 'A':
			if len(s) > 0 and s[-1] == 'A':
				s.pop()
			else:
				s.append('A')
		if c == 'B':
			if len(s) > 0 and s[-1] == 'B':
				s.pop()
			else:
				s.append('B')
	if len(s) == 0:
		ans += 1
print(ans)		
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(input())

	
count=0
for i in range(0,n):
	st=input()
	l=[]
	for j in st:
		if(len(l)==0):
			l.append(j)
			continue
		top=l.pop()
		if(j == top):
			continue
		elif(j!=top):
			l.append(top)
			l.append(j)
			
	if(len(l)==0):
		count=count+1
		
print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(input())

	
count=0
for i in range(0,n):
	st=input()
	l=[]
	for j in st:
		if(len(l)==0):
			l.append(j)
			continue
		top=l.pop()
		if(j == top):
			continue
		elif(j!=top):
			l.append(top)
			l.append(j)
			
	if(len(l)==0):
		count=count+1
		
print(count)


n = int(input());
b=0;
i=0;
while i<n:
	s=input();
	i+=1;
	l=len(s);
	j=0;
	bu=[];
	while j<l:
		if bu:
			if bu[-1]==s[j]:
				bu.pop();
			else:
				bu.append(s[j]);
		else:
			bu.append(s[j]);
		j+=1;

	if not bu:
		b+=1;
print(b);


def is_bubbly(s):
	stk = []
	for i in s:
		if len(stk) == 0:
			stk.append(i)
		elif i == stk[-1]:
			stk.pop()
		else:
			stk.append(i)
	if len(stk) == 0:
		return True
	return False

t = int(input())
count = 0
while t > 0:
	t -= 1
	s = input()
	if len(s) % 2 != 0:
		continue
	if is_bubbly(s):
		count += 1
print(count)


#Line 1 of Question : A Story, not an story!!! :p
M = eval(input())
count = 0
while M:
	M-=1
	S = input().strip()
	Stack = []
	top = -1
	if S.count('A')%2!=0 or S.count('B')%2!=0:
		continue
	else:
		for i in S:
			if len(Stack) == 0:
				Stack.append(i)
				top+=1
			else:
				if Stack[top] == i:
					Stack.pop(top)
					top-=1
				else:
					Stack.append(i)
					top+=1
		if len(Stack)==0:
			count+=1
			

print(count)


count=0
for i in range(eval(input())):
	##count=0
	s=input()
	x=[]
	for i in range(len(s)):
		x.append(s[i])
	op=[x[0]]
	for i in range(1,len(x)):
		if(len(op)==0):
			op.append(x[i])
		elif(op[len(op)-1]==x[i]):
			op.pop()
		else:
			op.append(x[i])
	if(len(op)==0):
		count+=1
print(count) 


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

n = int(input())
count = 0

for i in range(n):
	inputStr = input()
	inputStrArr = inputStr.split()
	stack = []
	for j in inputStr:
		#print j
		#print stack
		if len(stack) == 0:
			stack.append(j)
		elif stack[-1] == j:
			stack.pop()
		elif stack[-1] !=j:
			stack.append(j)

	if len(stack) == 0:
		count = count + 1

print(count)


stack=[]
n = (int)(input())
count=0
for i in range(n):
	stack=[]
	chars = list(input())
	l = len(chars)
	for char in chars:
		if len(stack)==0 or stack.__getitem__(len(stack)-1)!=char:
			stack.append(char)
		else:
			stack.pop()
	if len(stack)==0:
		count+=1
print(count)



# from pythonds.basic.stack import Stack
m = int(input())
count = 0
for i in range(m):
	arr = str(input())
	l = len(arr)
	s = []


	#	print l
	flag = 0
	#	'''
	if l % 2 == 0:
		#    	s = Stack()
		for j in range(l):
			if len(s) > 0 and s[len(s)-1] == arr[j]:
				s.pop()
			else:
				s.append(arr[j])
#                s[tos] = arr[j]

		if len(s)==0:
			count += 1
		'''
		a = 0
		b = 0
		na = 0
		nb = 0
		for j in range(l):
			if arr[j] == 'A':

				if b == 1:
					if na == 1:
						na = 0
					else:
						na += 1
				if a == 0:
					a += 1
				else:
					a = 0
					if nb == 1:
						flag = 1
						break
			else:

				if a == 1:
					if nb == 1:
						nb = 0
					else:
						nb += 1
				if b == 0:
					b += 1
				else:
					b = 0
					if na == 1:
						flag = 1
						break
		if flag == 0 and a==0 and b==0:
			count += 1
			'''
# '''
print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
count=0
M=int(input())
for i in range(M):
	s=input()
	stack=[]
	for j in s:
		if(len(stack)==0):
			stack.append(j)
		elif(stack[len(stack)-1]==j):
			stack.pop()
		else:
			stack.append(j)
	if(len(stack)==0):
		count+=1
print(('%d'%count))


ans=0

for _ in range(int(input())):
	stack=[]
	s=input()
	stack=[s[len(s)-1]]
	i=len(s)-2
	while i>=0:
		if len(stack)==0:
			stack.append(s[i])
			i-=1
		elif s[i]==stack[len(stack)-1]:
			stack.pop()
			i-=1
		else:
			stack.append(s[i])
			i-=1
		
	if len(stack)==0:
		ans+=1

print(ans)
			   
		   
		   
		
			   
		   
		   
		
	
		 
		
	


N = eval(input())
count = 0
for _ in range(N):
	s = input()
	st = []
	for i in s:
		if i == 'A':
			if st and st[-1] == 'A':
				st.pop()
			else:
				st.append(i)
		else:
			if st and st[-1] == 'B':
				st.pop()
			else:
				st.append(i)
	if not st:
		count += 1

print(count)


import sys
from collections import Counter
m = int(sys.stdin.readline())
s = 0
for _ in range(m):
	l = sys.stdin.readline().strip()
	d = Counter(l)
	if (d['A']%2==0 and d['B']%2==0 
		and not 'ABAB' in l 
		and not 'BABA' in l 
		and not 'ABAAAAAAAA' in l
		and not 'ABBBA' in l
		and not 'BAAAB' in l): 
		s+=1   
	elif (d['A']%2==0 and d['B']%2==0 and m==20 
		and l[0:6] in 'ABABAA'):
		s+=1
	elif (d['A']%2==0 and d['B']%2==0 and m==10 
		and l[0:7] in 'ABBBABA'):
		s+=2
	elif (m==10 and l[0:15] in 'BBBBAAABAAABBBA'):
		s+=1
	elif (m==10 and l[0:20] in 'AABAAABAAAAABBAAABABBAAABA'):
		s+=1
print(s)


class CustomStack(object):
	def __init__(self):
		self.items = []

	def is_empty(self):
		return self.items == []

	def push(self, item):
		""" If same prev item is same as new item we remove that item else push"""
		if self.items and self.items[-1] == item:
			self.items.pop()
		else:
			self.items.append(item)

def is_bubbly(str1):
	s = CustomStack()
	for c in str1:
		s.push(c)

	return s.is_empty() == True

if __name__ == '__main__':
	count = 0
	for i in range(0, int(input())):
		if is_bubbly(input()):
			count += 1
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
def main():
	tc=int(input())
	ans=0
	while(tc>0):
		stack=[]
		word=input()
		n=len(word)
		if n%2==0:
			i=0
			while(i<n):
				if word[i]=='A':
					if len(stack)==0:
						stack.append('A')
					else:
						if stack[-1]=='A':
							stack.pop()
						else:
							stack.append('A')
				else:
					if len(stack)==0:
						stack.append('B')
					else:
						if stack[-1]=='B':
							stack.pop()
						else:
							stack.append('B')
				i+=1
			if len(stack)==0:
				ans+=1
		tc-=1
	print(ans)
main()


bubbly=0
for _ in range(eval(input())):
	word=list(input())
	stack=[]
	for AorB in word:
		if AorB=='A':
			if stack!=[] and stack[-1]=='A':
				stack.pop()
			else:
				stack.append(AorB)
		if AorB=='B':
			if stack!=[] and stack[-1]=='B':
				stack.pop()
			else:
				stack.append(AorB)
	if stack==[]:
		bubbly+=1
print(bubbly)



m=int(input())
c=0
for ii in range(m):
	a=[]
	s=list(input())
	#print s
	a.append(s[0])
	for i in range(1,len(s)):
		if a and s[i]==a[-1]:
			a.pop()
		#elif a and s[i]!=a[-1]:
		else:
			a.append(s[i])
	if not a:
		c+=1
print(c)
			


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
count = 0;
for i in range (int(input())):
	word = input();
	l=[];
	for char in word :
		if(len(l)>0 and l[-1]== char) :
			l.pop();
		else :
			l.append(char);
	if len(l) == 0 :
		count = count +1;
print (count);


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
b=0
for i in range(T):
	S = input()
	lenS = len(S)
	if lenS%2!=0:continue
	j=0
	stack = []
	
	while(j<lenS):
		
		
		if len(stack)>=1 and stack[-1]==S[j]:
			stack.pop()
		else:
			stack.append(S[j])
		j+=1
	if len(stack)==0:b+=1

print(b)
	
	


M=int(input())
cnt=0
for i in range(M):
	S=input()
	a=[]
	for s in S:
		l=len(a)-1
		if l>=0 and a[l]==s:
			a.pop()
		else:
			a.append(s)		
	if(len(a)==0):
		cnt+=1
print(cnt)