IPL 2021 Finals are here and it is between the most successful team of the IPL Mumbai Indians and the team striving to garb their first trophy Royal Challengers Banglore. Rohit Sharma, captain of the team Mumbai Indians has the most experience in IPL finals, he feels lucky if he solves a programming question before the IPL finals. So, he asked the team's head coach  Mahela Jayawardene for a question. Question is, given a string S consisting only of opening and closing parenthesis 'ie '('  and ')',  the task is to find out the length of the longest valid parentheses substring.
NOTE: The length of the smallest valid substring ( ) is 2.
Example 1:
Input: S = "(()("
Output: 2
Explanation: The longest valid 
substring is "()". Length = 2.
Example 2:
Input: S = "()(())("
Output: 6
Explanation: The longest valid 
substring is "()(())". Length = 6.
Your Task:  
You don't need to read input or print anything. Complete the function findMaxLen() which takes S as input parameter and returns the max length.
Constraints:
1  ≤  |S|  ≤  10^{5}

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3



class Solution:

    def findMaxLen(ob, S):

        # code here 

Solutions:
class Solution:

	def findMaxLen(ob, s):
		if len(s) == 0:
			return 0
		stack = [-1]
		max_length = 0
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					curr_len = i - stack[-1]
					max_length = max(max_length, curr_len)
		return max_length


class Solution:

	def findMaxLen(ob, S):
		stack = []
		ans = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif len(stack) != 0 and S[stack[-1]] == '(':
				stack.pop()
				if len(stack) == 0:
					l = i + 1
				else:
					l = i - stack[-1]
				ans = max(ans, l)
			else:
				stack.append(i)
		return ans


class Solution:

	def findMaxLen(ob, S):
		x = 0
		stack = [-1]
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				else:
					x = max(x, i - stack[-1])
		return x


class Solution:

	def findMaxLen(self, S: str) -> int:
		stack = [-1]
		max_len = 0
		for (i, c) in enumerate(S):
			if c == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					max_len = max(max_len, i - stack[-1])
		return max_len


class Solution:

	def findMaxLen(ob, s):
		if len(s) <= 1:
			return 0
		curMax = 0
		longest = [0] * len(s)
		for i in range(1, len(s)):
			if s[i] == ')' and i - longest[i - 1] - 1 >= 0 and (s[i - longest[i - 1] - 1] == '('):
				longest[i] = longest[i - 1] + 2
				if i - longest[i - 1] - 2 >= 0:
					longest[i] += longest[i - longest[i - 1] - 2]
				else:
					longest[i] += 0
				curMax = max(longest[i], curMax)
		return curMax


class Solution:

	def findMaxLen(self, S):
		st = [-1]
		ans = 0
		for i in range(len(S)):
			if S[i] == '(':
				st.append(i)
			else:
				st.pop()
				if st:
					ans = max(ans, i - st[-1])
				else:
					st.append(i)
		return ans


class Solution:

	def findMaxLen(ob, S):
		(op, clo) = (0, 0)
		ans = 0
		n = len(S)
		for i in S:
			if i == '(':
				op += 1
			else:
				clo += 1
			if op == clo:
				ans = max(ans, op + clo)
			if clo > op:
				clo = 0
				op = 0
		(op, clo) = (0, 0)
		for i in range(n - 1, -1, -1):
			if S[i] == ')':
				clo += 1
			else:
				op += 1
			if op == clo:
				ans = max(ans, op + clo)
			if op > clo:
				clo = 0
				op = 0
		return ans


class Solution:

	def findMaxLen(ob, S):
		open_par = 0
		close_par = 0
		result = 0
		for ele in S:
			if ele == '(':
				open_par += 1
			else:
				close_par += 1
			if open_par == close_par:
				result = max(result, open_par + close_par)
			elif close_par > open_par:
				open_par = 0
				close_par = 0
		open_par = 0
		close_par = 0
		for ele in range(len(S) - 1, -1, -1):
			if S[ele] == '(':
				open_par += 1
			else:
				close_par += 1
			if open_par == close_par:
				result = max(result, open_par + close_par)
			elif close_par < open_par:
				open_par = 0
				close_par = 0
		return result


class Solution:

	def findMaxLen(ob, string):
		n = len(string)
		stk = []
		stk.append(-1)
		result = 0
		for i in range(n):
			if string[i] == '(':
				stk.append(i)
			else:
				if len(stk) != 0:
					stk.pop()
				if len(stk) != 0:
					result = max(result, i - stk[len(stk) - 1])
				else:
					stk.append(i)
		return result


class Solution:

	def findMaxLen(ob, s):
		stack = []
		i = 0
		ans = 0
		curr = 0
		while i < len(s):
			if s[i] == '(':
				stack.append(curr)
				curr = 0
			elif len(stack) == 0:
				curr = 0
			else:
				curr = curr + stack.pop() + 2
				ans = max(ans, curr)
			i += 1
		return ans


class Solution:

	def findMaxLen(ob, S):
		l = [-1]
		l1 = 0
		for (i, p) in enumerate(S):
			if p == '(':
				l.append(i)
			else:
				l.pop()
				if not l:
					l.append(i)
				else:
					l1 = max(l1, i - l[-1])
		return l1


class Solution:

	def findMaxLen(ob, S):
		lst = [-1]
		lv = 0
		for (i, p) in enumerate(S):
			if p == '(':
				lst.append(i)
			else:
				lst.pop()
				if not lst:
					lst.append(i)
				else:
					lv = max(lv, i - lst[-1])
		return lv


class Solution:

	def findMaxLen(ob, S):
		n = len(S)
		left = [0] * n
		right = [0] * n
		st = []
		for i in range(n):
			if S[i] == '(':
				st.append(i)
			elif len(st) > 0:
				left[i] = i - st[-1] + 1 + left[st[-1] - 1] if st[-1] - 1 >= 0 else st[-1] + 1
				st.pop()
		st = []
		for i in range(n - 1, -1, -1):
			if S[i] == ')':
				st.append(i)
			elif len(st) > 0:
				right[i] = st[-1] - i + 1 + right[st[-1] + 1] if st[-1] + 1 < n else st[-1] - i + 1
				st.pop()
		ans = right[0]
		for i in range(1, n):
			ans = max(ans, left[i - 1] + right[i])
		return ans


class Solution:

	def findMaxLen(ob, S):
		stk = []
		i = 0
		while i < len(S):
			if S[i] == '(':
				stk.append('(')
			elif len(stk) == 0:
				stk.append(')')
			elif stk[-1] == '(':
				stk.pop()
				stk.append('2')
			else:
				c = '0'
				while len(stk) > 0 and stk[-1].isdigit():
					c = str(int(c) + int(stk.pop()))
				if len(stk) == 0:
					stk.append(c)
					stk.append(')')
				elif stk[-1] == '(':
					stk.pop()
					stk.append(str(int(c) + 2))
				else:
					stk.append(c)
					stk.append(')')
			i += 1
		ans = 0
		x = 0
		while len(stk) > 0:
			if stk[-1].isdigit():
				x += int(stk.pop())
			else:
				ans = max(ans, x)
				x = 0
				stk.pop()
		ans = max(ans, x)
		return ans


class Solution:

	def findMaxLen(ob, s):
		n = len(s)
		left = right = maxlength = 0
		for i in range(n):
			if s[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				maxlength = max(maxlength, 2 * right)
			elif right > left:
				left = right = 0
		left = right = 0
		for i in range(n - 1, -1, -1):
			if s[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				maxlength = max(maxlength, 2 * left)
			elif left > right:
				left = right = 0
		return maxlength


class Solution:

	def findMaxLen(ob, S):
		st = [-1]
		maxi = 0
		l = len(S)
		for i in range(l):
			if S[i] == '(':
				st.append(i)
			else:
				st.pop()
				if st == []:
					st.append(i)
				else:
					maxi = max(maxi, i - st[-1])
		return maxi


class Solution:

	def findMaxLen(ob, S):
		maxi = 0
		summa = 0
		stack = []
		for item in S:
			if item == '(':
				stack.append(summa)
				summa = 0
			elif not stack:
				summa = 0
			else:
				summa += 2 + stack.pop()
				maxi = max(maxi, summa)
		return maxi


class Solution:

	def findMaxLen(ob, S):
		maxi = 0
		summa = 0
		stack = []
		for item in S:
			if stack and stack[-1][0] == '(' and (item == ')'):
				summa += 2 + stack.pop()[1]
				maxi = max(maxi, summa)
			else:
				stack.append([item, summa])
				summa = 0
		return maxi


class Solution:

	def findMaxLen(ob, s):
		(l, x) = ([], [])
		for i in range(len(s)):
			l.append(s[i])
		for i in range(0, len(s)):
			if l[i] == '(':
				x.append(i)
			elif len(x) > 0 and l[x[-1]] == '(':
				x.pop()
			else:
				x.append(i)
		(m, t) = (0, 0)
		a = len(s)
		while len(x) > 0:
			t = x.pop()
			m = max(m, a - t - 1)
			a = t
		return max(a, m)


class Solution:

	def findMaxLen(ob, S):
		x = 0
		stack = [-1]
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				else:
					x = max(x, i - stack[-1])
		return x
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))


class Solution:

	def findMaxLen(ob, S):
		(l, r) = (0, 0)
		maxlen = 0
		for p in S:
			if p == '(':
				l += 1
			else:
				r += 1
			if l == r:
				maxlen = max(maxlen, l + r)
			elif r > l:
				l = r = 0
		l = r = 0
		for p in reversed(S):
			if p == '(':
				l += 1
			else:
				r += 1
			if l == r:
				maxlen = max(maxlen, l + r)
			elif l > r:
				l = r = 0
		return maxlen


class Solution:

	def findMaxLen(ob, S):
		st = []
		vp = [0] * len(S)
		for i in range(len(S)):
			if S[i] == '(':
				st.append(i)
			elif len(st) != 0:
				pi = st.pop()
				vp[i] = 1
				vp[pi] = 1
		(c, mc) = (0, 0)
		for p in vp:
			if p:
				c += 1
			else:
				if c > mc:
					mc = c
				c = 0
		if c > mc:
			return c
		return mc


class Solution:

	def findMaxLen(ob, S):
		stack = []
		result = []
		n = len(S)
		for i in range(len(S)):
			if S[i] == '(':
				stack.append([S[i], i])
			elif S[i] == ')':
				if len(stack) == 0:
					stack.append([S[i], i])
				elif stack[-1][0] == '(':
					stack.pop()
				else:
					stack.append([S[i], i])
		if len(stack) == 0:
			return n
		for i in range(len(stack) - 1, -1, -1):
			jk = n - stack[i][1] - 1
			result.append(jk)
			n = stack[i][1]
			if i == 0:
				result.append(n)
		return max(result)


class Solution:

	def findMaxLen(ob, S):
		op = 0
		mx = 0
		cl = 0
		for i in S:
			if i == '(':
				op = op + 1
			else:
				cl = cl + 1
			if op == cl:
				mx = max(mx, 2 * op)
			elif cl >= op:
				cl = op = 0
		op = 0
		cl = 0
		for i in range(len(S) - 1, 0, -1):
			if S[i] == '(':
				op = op + 1
			else:
				cl = cl + 1
			if cl == op:
				mx = max(mx, 2 * op)
			elif op > cl:
				cl = op = 0
		return mx


class Solution:

	def findMaxLen(ob, a):
		s = []
		for i in range(len(a)):
			if s and (a[i] == ')' and a[s[-1]] == '('):
				s.pop()
			else:
				s.append(i)
		e = len(a)
		res = 0
		while s:
			t = s.pop()
			res = max(res, e - t - 1)
			e = t
		return max(res, e)


class Solution:

	def findMaxLen(ob, s):
		n = len(s)
		maxi = 0
		length = 0
		stack = [-1]
		m = 1
		for i in range(n):
			if s[i] == '(':
				stack.append(i)
				m += 1
			else:
				stack.pop(-1)
				m -= 1
				if m == 0:
					stack.append(i)
					m += 1
				else:
					maxi = max(maxi, i - stack[-1])
		return maxi


class Solution:

	def findMaxLen(ob, S):
		req = []
		stack = []
		count = 0
		longest = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif stack:
				req.append(stack.pop())
				req.append(i)
		req.sort()
		for i in range(1, len(req)):
			if req[i] - 1 == req[i - 1]:
				if count == 0:
					count = 2
				else:
					count += 1
			else:
				longest = max(longest, count)
				count = 0
		longest = max(longest, count)
		return longest


class Solution:

	def findMaxLen(ob, S):
		m = 0
		s = [-1]
		n = len(S)
		for i in range(n):
			if S[i] == '(':
				s.append(i)
			else:
				s.pop()
				if len(s) != 0:
					d = i - s[-1]
					if d > m:
						m = d
				else:
					s.append(i)
		return m


class Solution:

	def findMaxLen(ob, S):
		if S == '':
			return 0
		stack = []
		max_l = 0
		stack.append(-1)
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			if S[i] == ')':
				if len(stack) == 1:
					stack.pop()
					stack.append(i)
					continue
				stack.pop()
				max_l = max(max_l, i - stack[-1])
		return max_l


class Solution:

	def findMaxLen(ob, s):
		open = 0
		close = 0
		ans = 0
		for i in s:
			if i == '(':
				open += 1
			if i == ')':
				close += 1
			if open == close:
				ans = max(ans, 2 * open)
			if close > open:
				open = 0
				close = 0
		(open, close) = (0, 0)
		for i in s[::-1]:
			if i == '(':
				open += 1
			if i == ')':
				close += 1
			if open == close:
				ans = max(ans, 2 * open)
			if close < open:
				open = 0
				close = 0
		return ans


class Solution:

	def findMaxLen(ob, S):
		if len(S) < 2:
			return 0
		ans = 0
		stack = [-1]
		for (i, v) in enumerate(S):
			if v == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					ans = max(ans, i - stack[-1])
		return ans


class Solution:

	def findMaxLen(ob, S):
		M = 0
		lc = 0
		rc = 0
		for i in range(len(S)):
			if S[i] == '(':
				lc += 1
			else:
				rc += 1
			if lc == rc:
				if M < lc * 2:
					M = lc * 2
			if rc > lc:
				lc = 0
				rc = 0
		lc = 0
		rc = 0
		for j in range(len(S) - 1, -1, -1):
			if S[j] == ')':
				rc += 1
			else:
				lc += 1
			if lc == rc:
				if M < lc * 2:
					M = lc * 2
			if lc > rc:
				rc = 0
				lc = 0
		return M


class Solution:

	def findMaxLen(ob, S):
		ans = 0
		n = len(S)
		right = left = 0
		for i in range(n):
			if S[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				ans = max(ans, 2 * left)
			elif right > left:
				right = left = 0
		right = left = 0
		for i in range(n - 1, -1, -1):
			if S[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				ans = max(ans, 2 * left)
			elif left > right:
				right = left = 0
		return ans


class Solution:

	def findMaxLen(ob, S):
		stack = [-1]
		res = 0
		for (idx, char) in enumerate(S):
			if char == '(':
				stack.append(idx)
			else:
				if len(stack) != 0:
					stack.pop()
				if len(stack) != 0:
					res = max(res, idx - stack[-1])
				else:
					stack.append(idx)
		return res


class Solution:

	def findMaxLen(ob, s):
		st = []
		i = 0
		res = 0
		pos = 0
		while i < len(s):
			if s[i] == '(':
				st.append(pos)
				pos = 0
			elif len(st) == 0:
				pos = 0
			else:
				pos = pos + st.pop() + 2
				res = max(res, pos)
			i += 1
		return res


class Solution:

	def findMaxLen(ob, S):
		li = []
		ans = 0
		li.append(0)
		n = len(S)
		i = 1
		while i < n:
			res = 0
			while i < n and S[i] == ')':
				if len(li) > 0 and S[li[-1]] == '(':
					li.pop()
					i += 1
				else:
					break
			if i < n:
				li.append(i)
				i += 1
		(start, end) = (-1, len(S))
		for j in range(len(li)):
			ans = max(ans, abs(li[j] - start - 1))
			start = li[j]
		return max(ans, end - start - 1)


class Solution:

	def findMaxLen(ob, S):
		n = len(S)
		(o, c, a) = (0, 0, 0)
		for i in range(n):
			if S[i] == '(':
				o += 1
			else:
				c += 1
			if o == c:
				a = max(a, o + c)
			if c > o:
				(o, c) = (0, 0)
		(o, c) = (0, 0)
		i = n - 1
		while i >= 0:
			if S[i] == '(':
				o += 1
			else:
				c += 1
			if o == c:
				a = max(a, o + c)
			if o > c:
				(o, c) = (0, 0)
			i -= 1
		return a


class Solution:

	def findMaxLen(self, S):
		stp = [-1]
		stc = ['x']
		ans = 0
		for (i, c) in enumerate(S):
			if c == ')' and stc[-1] == '(':
				stc.pop()
				stp.pop()
				ans = max(ans, i - stp[-1])
			else:
				stp.append(i)
				stc.append(c)
		return ans


class Solution:

	def findMaxLen(ob, S):
		stack = [0]
		lon = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(0)
			elif len(stack) > 1:
				c = stack.pop()
				stack[-1] += c + 2
				lon = max(lon, stack[-1])
			else:
				stack = [0]
		return lon


class Solution:

	def findMaxLen(ob, S):
		stack = []
		count = []
		toPop = 0
		ans = 0
		prev = 0
		for c in S:
			if len(stack) > 1 and type(stack[-1]) == int and (type(stack[-2]) == int):
				stack[-2] += stack[-1]
				stack.pop()
			if c in '([{':
				stack.append(c)
			if stack and type(stack[-1]) == str and (stack[-1] + c in {'()', '[]', '{}'}):
				stack.pop()
				if stack and type(stack[-1]) == int:
					stack[-1] += 2
				else:
					stack.append(2)
				continue
			if len(stack) > 1 and type(stack[-1]) == int and (type(stack[-2]) == str) and (stack[-2] + c in {'()', '[]', '{}'}):
				temp = stack[-1]
				stack.pop()
				stack.pop()
				stack.append(temp + 2)
				continue
			if c in ')':
				stack.append(c)
		if len(stack) > 1 and type(stack[-1]) == int and (type(stack[-2]) == int):
			stack[-2] += stack[-1]
			stack.pop()
		for i in stack:
			if type(i) == int and i > ans:
				ans = i
		return ans


class Solution:

	def findMaxLen(ob, S):
		from collections import deque
		q = deque()
		q.append([')', 0])
		maxi = 0
		for i in S:
			if i == '(':
				q.append([i, 0])
			if i == ')':
				if i == q[-1][0]:
					q.append([i, 0])
				else:
					q[-2][1] += q[-1][1] + 2
					q.pop()
		while q:
			(asd, asd1) = q.pop()
			maxi = max(maxi, asd1)
		return maxi


class Solution:

	def findMaxLen(self, s):
		stack = []
		currValidLen = 0
		maxLenSF = 0
		for c in s:
			if c == '(':
				stack.append(currValidLen)
				currValidLen = 0
			else:
				if len(stack) == 0:
					currValidLen = 0
					continue
				currValidLen += stack.pop() + 2
			maxLenSF = max(maxLenSF, currValidLen)
		return maxLenSF


class Solution:

	def findMaxLen(ob, S):
		stk = []
		stk.append(-1)
		res = 0
		for i in range(len(S)):
			if S[i] == '(':
				stk.append(i)
			else:
				if len(stk) != 0:
					stk.pop()
				if len(stk) != 0:
					res = max(res, i - stk[len(stk) - 1])
				else:
					stk.append(i)
		return res


class Solution:

	def findMaxLen(ob, s):
		n = len(s)
		stack = []
		stack.append(-1)
		res = 0
		for i in range(n):
			if s[i] == '(':
				stack.append(i)
			else:
				if len(stack) != 0:
					stack.pop()
				if len(stack) != 0:
					res = max(res, i - stack[-1])
				else:
					stack.append(i)
		return res


def FUN(A):
	Stack = []
	Ind = []
	n = len(A)
	for i in range(n):
		if A[i] == ')':
			if Stack:
				if Stack[-1] == '(':
					Stack.pop()
					Ind.pop()
				else:
					Stack.append(A[i])
					Ind.append(i)
			else:
				Stack.append(A[i])
				Ind.append(i)
		else:
			Stack.append(A[i])
			Ind.append(i)
	Ans = 0
	if Ind:
		Ans = max(Ans, Ind[0] - 0)
		Ans = max(Ans, n - 1 - Ind[-1])
	else:
		Ans = n
	for i in range(len(Ind) - 1):
		Ans = max(Ans, Ind[i + 1] - Ind[i] - 1)
	return Ans

class Solution:

	def findMaxLen(ob, S):
		return FUN(S)


class Solution:

	def findMaxLen(ob, S):
		a = S
		b = []
		b.append(-1)
		maxi = 0
		for i in range(len(a)):
			if a[i] == '(':
				b.append(i)
			elif a[i] == ')':
				b.pop()
				if len(b) != 0:
					m1 = i - b[-1]
					maxi = max(m1, maxi)
				else:
					b.append(i)
		return maxi
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))


class Solution:

	def findMaxLen(ob, S):
		index = 0
		stack = []
		value = 0
		cur = 0
		while index < len(S):
			if S[index] == '(':
				stack.append(cur)
				cur = 0
			elif len(stack) == 0:
				cur = 0
			else:
				cur = cur + stack.pop() + 2
				value = max(value, cur)
			index += 1
		return value
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))


class Solution:

	def findMaxLen(ob, S):
		stk = []
		ans = [0] * len(S)
		for i in range(0, len(S)):
			if S[i] == '(':
				stk.append((S[i], i))
				continue
			if len(stk) > 0 and stk[-1][0] == '(':
				ans[stk[-1][1]] = 1
				ans[i] = 1
				stk.pop(-1)
		ans_main = 0
		temp_ans = 0
		for i in ans:
			if i == 1:
				temp_ans += 1
				ans_main = max(ans_main, temp_ans)
			else:
				temp_ans = 0
		return ans_main
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))


class Solution:

	def findMaxLen(ob, string):
		n = len(string)
		stk = []
		stk.append(-1)
		result = 0
		for i in range(n):
			if string[i] == '(':
				stk.append(i)
			else:
				if len(stk) != 0:
					stk.pop()
				if len(stk) != 0:
					result = max(result, i - stk[len(stk) - 1])
				else:
					stk.append(i)
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))


class Solution:

	def findMaxLen(ob, S):
		maxlen = 0
		count = 0
		stack = [-1]
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif S[i] == ')' and len(stack) > 0:
				stack.pop()
				if len(stack) > 0:
					maxlen = max(maxlen, i - stack[len(stack) - 1])
				else:
					stack.append(i)
		return maxlen
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.findMaxLen(S))