Lira is now very keen on compiler development. :) 
She knows that one of the most important components of a compiler, is its parser.
A parser is, in simple terms, a software component that processes text, and checks it's semantic correctness, or, if you prefer, if the text is properly built.
As an example, in declaring and initializing an integer, in C/C++, you can't do something like:
int = x ;4
as the semantics of such statement is incorrect, as we all know that the datatype must precede an identifier and only afterwards should come the equal sign and the initialization value, so, the corrected statement should be:
int x = 4;
Today, Lira is concerned with an abstract instruction which is composed of the characters "<" and ">" , which she will use on the design of her language, L++ :D.
She is using it as an abstraction for generating XML code Tags in an easier fashion and she understood that, for an expression to be valid, a "<" symbol must always have a corresponding ">" character somewhere (not necessary immediately) after it. Moreover, each ">" symbol should correspond to exactly one "<" symbol.
So, for instance, the instructions:
<<>> 
<> 
<><> 
are all valid. While:
>> 
><>< 
are not.
Given some expressions which represent some instructions to be analyzed by Lira's compiler, you should tell the length of the longest prefix of each of these expressions that is valid, or 0 if there's no such a prefix.

-----Input-----
Input will consist of an integer T denoting the number of test cases to follow.
Then, T strings follow, each on a single line, representing a possible expression in L++.

-----Output-----
For each expression you should output the length of the longest prefix that is valid or 0 if there's no such a prefix. 


-----Constraints-----
- 1 ≤ T ≤ 500
- 1 ≤ The length of a single expression ≤ 106
- The total size all the input expressions is no more than 5*106

-----Example-----
Input:
3
<<>>
><
<>>>
Output:
4
0
2

Difficulty: MEDIUM
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	s = input()
	l = []
	f = 0
	m = 0
	for j in s:
		if j == '<':
			l.append('<')
		elif j == '>' and len(l) > 0:
			l = l[:-1]
			f = f + 2
			if l == []:
				m = f
		else:
			break
	print(m)


for j in range(int(input())):
	c = 0
	a = 0
	s = input()
	for i in range(len(s)):
		if s[i] == '<':
			c += 1
		else:
			c -= 1
		if c == 0:
			a = i + 1
		if c == -1:
			break
	print(a)


t = int(input())
for i in range(t):
	total = 0
	temp = 0
	str = input()
	for (i, ch) in enumerate(str):
		if ch == '<':
			temp += 1
		elif ch == '>':
			temp -= 1
		if temp == 0:
			total = i + 1
		elif temp < 0:
			break
	print(total)


t = int(input())
for i in range(0, t):
	stringa = input()
	result = 0
	counter = 0
	appoggio = 0
	if stringa[0] == '>':
		print(0)
	else:
		for s in stringa:
			if s == '<':
				counter += 1
			if s == '>':
				counter = counter - 1
				result += 2
			if counter == 0:
				appoggio = result
			if counter < 0:
				break
		print(appoggio)


for t in range(int(input())):
	count = 0
	ans = 0
	s = input()
	for i in range(len(s)):
		if s[i] == '<':
			count += 1
		else:
			count -= 1
		if count == 0:
			ans = i + 1
		if count == -1:
			break
	print(ans)


t = int(input())
for test in range(t):
	expression = list(input())
	available_left_arrow = 0
	streak = 0
	max_streak = 0
	for exp in expression:
		if exp == '<':
			available_left_arrow += 1
		else:
			if available_left_arrow <= 0:
				break
			available_left_arrow -= 1
			if available_left_arrow == 0:
				max_streak = max_streak + 2 + streak
				streak = 0
			else:
				streak += 2
	print(max_streak)


t = int(input())
while t > 0:
	b = c = d = 0
	t -= 1
	s = input()
	for i in s:
		if i == '<':
			b += 1
		elif i == '>':
			b -= 1
			if b < 0:
				break
			elif b == 0:
				c += 2 + d
				d = 0
			else:
				d += 2
	print(c)


for _ in range(int(input())):
	a = input()
	k = 0
	c = 0
	l = 0
	for i in a:
		if i == '<':
			k += 1
		elif k > 0:
			k -= 1
			c += 1
			if k == 0:
				l += c * 2
				c = 0
		else:
			break
	print(l)


def longestValidPrefixParentheses(s: str) -> int:
	maxLength = 0
	stack = []
	size = len(s)
	for i in range(size):
		if s[i] == '<':
			stack.append(i)
			continue
		if not stack:
			break
		stack.pop()
		if not stack:
			maxLength = max(maxLength, i + 1)
	return maxLength
n = int(input())
for _ in range(n):
	print(longestValidPrefixParentheses(input()))


def solve(S):
	ans = 0
	t = 0
	l = []
	for a in S:
		t += 1
		if a == '<':
			l.append(a)
		if a == '>':
			if len(l) == 0:
				return ans
			if len(l) > 0:
				l.pop()
				if len(l) == 0:
					ans = t
	return ans
T = int(input())
ls = list()
for i in range(T):
	print(solve(input()))


def Solve(s, n):
	(sum, ans, cnt) = (0, 0, 0)
	for i in range(n):
		if s[i] == '<':
			sum += 1
			cnt += 1
		else:
			sum = sum - 1
		if sum == 0:
			ans = ans + cnt * 2
			cnt = 0
		if sum < 0:
			break
	return ans
for _ in range(int(input())):
	s = input()
	print(Solve(s, len(s)))


test = int(input())
for z in range(test):
	s = input()
	cnt = 0
	ans = 0
	l = 0
	for i in s:
		if i == '<':
			cnt += 1
		else:
			cnt -= 1
			l += 2
		if cnt == 0:
			ans = l
		if cnt < 0:
			break
	print(ans)


from sys import stdin, stdout

def main():
	numberOfCases = int(stdin.readline())
	for i in range(0, numberOfCases):
		arr = [char for char in stdin.readline().strip()]
		starter = []
		count = 0
		currentCount = 0
		for element in arr:
			if element == '<':
				starter.append(element)
			else:
				if len(starter) == 0:
					break
				starter.pop()
				if len(starter) == 0:
					count = count + 2 + currentCount
					currentCount = 0
				else:
					currentCount += 2
		print(count)

def __starting_point():
	main()
__starting_point()


for _ in range(int(input())):
	s = input()
	st = []
	(temp, count) = (0, 0)
	for i in s:
		if i == '<':
			st.append('<')
		elif len(st) == 0:
			break
		else:
			st.pop()
			if len(st) == 0:
				count += 2 + temp
				temp = 0
			else:
				temp += 2
	print(count)


def longest_valid_prefix(s):
	stack = []
	length = 0
	for i in range(len(s)):
		if s[i] == '<':
			stack.append(s[i])
		else:
			if not stack:
				break
			stack.pop()
			if not stack:
				length = i + 1
	return length

def longest_valid_prefix1(s):
	stack = [-1]
	max_size = 0
	for i in range(len(s)):
		if s[i] == '<':
			stack.append(i)
		else:
			stack.pop()
			if stack:
				if len(stack) == 1 and stack[0] == -1 and (i - stack[-1] > max_size):
					max_size = i - stack[-1]
			else:
				break
	return max_size

def longest_valid_substring(s):
	stack = [-1]
	be = en = max_size = 0
	for i in range(len(s)):
		if s[i] == '<':
			stack.append(i)
		else:
			stack.pop()
			if stack:
				if i - stack[-1] > max_size:
					en = i + 1
					be = stack[-1] + 1
					max_size = en - be
			else:
				stack.append(i)
	return s[be:en]
T = int(input())
for _ in range(T):
	print(longest_valid_prefix1(input()))


for i in range(int(input())):
	x = input()
	(a, c) = (0, 0)
	for (j, i) in enumerate(x):
		if i == '<':
			c += 1
		else:
			c -= 1
		if c == 0:
			a = j + 1
		if c < 0:
			break
	print(a)


t = int(input())
for _ in range(t):
	s = input()
	l = []
	c = 0
	flag = 0
	for i in range(len(s)):
		if s[i] == '<':
			c += 1
		else:
			c -= 1
		if c == 0:
			flag = i + 1
		if c < 0:
			break
	print(flag)


def longest_valid_prefix(s):
	stack = []
	length = 0
	for i in range(len(s)):
		if s[i] == '<':
			stack.append(s[i])
		else:
			if not stack:
				break
			stack.pop()
			if not stack:
				length = i + 1
	return length
T = int(input())
for _ in range(T):
	print(longest_valid_prefix(input()))


T = int(input())
for k in range(0, T):
	string = input()
	count = 0
	max_length = 0
	for k in range(0, len(string)):
		if string[k] == '<':
			count += 1
		elif string[k] == '>':
			count -= 1
		else:
			break
		if count == 0:
			max_length = k + 1
		elif count < 0:
			break
	print(max_length)


from queue import LifoQueue
for _ in range(int(input())):
	a = input()
	b = 0
	d = 0
	s = []
	for i in range(len(a)):
		if a[i] == '<':
			s.append(a[i])
		elif not s:
			break
		else:
			x = s.pop()
			if not s:
				b = i + 1
	print(b)


t = int(input())
for j in range(t):
	s = input()
	st = []
	ans = 0
	for i in range(len(s)):
		if s[i] == '>':
			if len(st) != 0 and st[-1] == '<':
				st.pop()
				if len(st) == 0:
					ans = i + 1
			else:
				break
		else:
			st.append('<')
	print(ans)


for _ in range(int(input())):
	s = input()
	check = 0
	value = 0
	for i in range(len(s)):
		if s[i] == '<':
			check += 1
		else:
			check -= 1
		if check == 0:
			value = i + 1
		if check < 0:
			break
	print(value)


def solve(S):
	mystack = []
	ans = 0
	for i in range(len(S)):
		if S[i] == '<':
			mystack.append('<')
		elif len(mystack) == 0:
			return ans
		else:
			mystack.pop()
			if len(mystack) == 0:
				ans = i + 1
	return ans
T = int(input())
for j in range(T):
	print(solve(input()))


for i in range(int(input())):
	c = 0
	ans = 0
	n = input()
	for i in range(len(n)):
		if n[i] == '<':
			c += 1
		else:
			c -= 1
		if c == 0:
			ans = i + 1
		if c == -1:
			break
	print(ans)


n = int(input())
for i in range(n):
	char = input()
	lenght = 0
	stack = []
	close = []
	for i in range(len(char)):
		if char[i] == '<':
			stack.append(char[i])
		elif len(stack) == 0:
			break
		else:
			stack.pop()
			if len(stack) == 0:
				lenght = i + 1
	print(lenght)


def parser(l):
	n = len(l)
	if l[0] == '>':
		return 0
	(c, i, t) = (0, 0, 0)
	k = []
	while i < n:
		if l[i] == '<':
			k.append(i)
		else:
			if len(k) == 0:
				return c
			k.pop()
			t += 2
			if len(k) == 0:
				c += t
				t = 0
		i += 1
	return c
for x in range(int(input())):
	s = list(input())
	print(parser(s))


for y in range(int(input())):
	s = input()
	st = []
	i = -1
	a = 0
	for x in range(len(s)):
		if i == -1 and s[x] == '>':
			break
		elif s[x] == '<':
			st.append('<')
			i += 1
		elif s[x] == '>':
			st.pop()
			i -= 1
		if i == -1:
			a = x + 1
	print(a)


n = int(input())
for i in range(n):
	count = 0
	temp = 0
	a = input()
	for (br, ch) in enumerate(a):
		if ch == '<':
			temp += 1
		elif ch == '>':
			temp -= 1
		if temp == 0:
			count = br + 1
		elif temp < 0:
			break
	print(count)


t = int(input())
for _ in range(t):
	x = input()
	t = 0
	cnt = 0
	lst = []
	for i in x:
		if i == '<':
			lst.append(i)
		elif len(lst) == 0:
			break
		else:
			lst.pop()
			if len(lst) == 0:
				cnt += 2 + t
				t = 0
			else:
				t += 2
	print(cnt)


for i in range(int(input())):
	s = input()
	stack = []
	ans = 0
	c = 0
	for i in range(len(s)):
		if s[i] == '<':
			stack.append(s[i])
			c += 1
		elif len(stack) == 0 or stack[-1] != '<':
			break
		else:
			stack.pop()
			if len(stack) == 0:
				ans += 2 * c
				c = 0
	print(ans)


T = int(input())
for _ in range(T):
	str1 = input()
	stack = []
	ans = 0
	cnt = 0
	token = []
	flag = 0
	for i in str1:
		if i == '<':
			stack.append(i)
		elif len(stack) != 0:
			stack.pop()
			cnt += 1
			if len(stack) == 0:
				ans = ans + cnt * 2
				cnt = 0
		else:
			print(ans)
			flag = 1
			break
	if flag == 0:
		print(ans)


n = int(input())
for i in range(n):
	count = 0
	ans = 0
	m = input()
	for j in range(len(m)):
		if m[j] == '<':
			count += 1
		else:
			count -= 1
		if count == 0:
			ans = j + 1
		if count == -1:
			break
	print(ans)


T = int(input())
while T:
	check = []
	s = input()
	cur = 0
	long_prifix = 0
	for i in s:
		cur += 1
		if i == '<':
			check.append(i)
		elif i == '>' and len(check):
			check.pop()
			if not check:
				long_prifix = cur
		else:
			break
	print(long_prifix)
	T -= 1


tc = int(input())
for q in range(tc):
	arr = input()
	stack = []
	maxx = 0
	counter = 0
	for i in arr:
		counter += 1
		if i == '<':
			stack.append(i)
		elif i == '>' and len(stack):
			stack.pop()
			if not stack:
				maxx = counter
		else:
			break
	print(maxx)


def parser(l):
	n = len(l)
	if l[0] == '>':
		return 0
	(count, i, temp) = (0, 0, 0)
	k = []
	while i < n:
		if l[i] == '<':
			k.append(i)
		else:
			if len(k) == 0:
				return count
			k.pop()
			temp += 2
			if len(k) == 0:
				count += temp
				temp = 0
		i += 1
	return count
for _ in range(int(input())):
	s = list(input())
	print(parser(s))


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


def compiler(string):
	t = 0
	ans = 0
	for i in range(len(string)):
		if string[i] == '<':
			t += 1
		else:
			t -= 1
			if t == 0:
				ans = max(ans, i + 1)
			elif t < 0:
				break
	return ans
t = int(input())
while t:
	string = input()
	print(compiler(string))
	t -= 1


T = int(input())
for k in range(0, T):
	string = input()
	count = 0
	length = 0
	max_length = 0
	for char in string:
		if char == '<':
			count += 1
		elif char == '>':
			count -= 1
			length += 2
		else:
			break
		if count == 0:
			max_length = length
		elif count < 0:
			break
	print(max_length)


t = int(input())
while t:
	t -= 1
	s = input()
	count = 0
	a = 0
	d = []
	for i in s:
		if i == '<':
			d.append('<')
		elif i == '>' and d == []:
			break
		else:
			d.pop(0)
			if d == []:
				count += 2 + a
				a = 0
			else:
				a += 2
	print(count)


t = int(input())
while t:
	a = list(map(str, input()))
	b = []
	(c, ans) = (0, 0)
	for i in range(len(a)):
		if a[i] == '<':
			b.append(a[i])
			c += 1
		elif len(b) == 0 or b[-1] != '<':
			break
		else:
			b.pop()
			if len(b) == 0:
				ans += 2 * c
				c = 0
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	l = []
	for i in range(0, len(s)):
		if s[i] == '>':
			if len(l) != 0 and l[-1] == '<':
				l.pop()
				if len(l) == 0:
					count = i + 1
			else:
				break
		else:
			l.append('<')
	print(count)


t = int(input())
while t:
	t -= 1
	s = input()
	ans = 0
	stk = []
	n = len(s)
	for i in range(n):
		if s[i] == '<':
			stk.append(s[i])
		else:
			if stk == []:
				break
			stk.pop()
			if stk == []:
				ans = i + 1
	print(ans)


for _ in range(int(input())):
	s = input()
	a = 0
	su = 0
	for i in range(len(s)):
		if s[i] == '<':
			su += 1
		else:
			su -= 1
		if su == 0:
			a = i + 1
		if su < 0:
			break
	print(a)


T = int(input())
for k in range(0, T):
	string = input()
	count = 0
	length = 0
	max_length = 0
	valid = True
	for i in range(0, len(string)):
		if string[i] == '<':
			count += 1
		elif string[i] == '>':
			count -= 1
			length += 2
		else:
			print(length)
			valid = False
			break
		if count == 0:
			max_length = length
		elif count < 0:
			print(max_length)
			valid = False
			break
	if valid == True:
		print(max_length)


for _ in range(int(input())):
	s = input()
	diff = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == '<':
			diff += 1
		else:
			diff -= 1
		if diff == 0:
			ans = i + 1
		if diff < 0:
			break
	print(ans)