You are given a string $s$, consisting of brackets of two types: '(', ')', '[' and ']'.

A string is called a regular bracket sequence (RBS) if it's of one of the following types:

empty string;

'(' + RBS + ')';

'[' + RBS + ']';

RBS + RBS.

where plus is a concatenation of two strings.

In one move you can choose a non-empty subsequence of the string $s$ (not necessarily consecutive) that is an RBS, remove it from the string and concatenate the remaining parts without changing the order.

What is the maximum number of moves you can perform?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Each of the next $t$ lines contains a non-empty string, consisting only of characters '(', ')', '[' and ']'. The total length of the strings over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase print a single integer — the maximum number of moves you can perform on a given string $s$.


-----Examples-----

Input
5
()
[]()
([)]
)]([
)[(]
Output
1
2
2
0
1


-----Note-----

In the first example you can just erase the whole string.

In the second example you can first erase the brackets on positions $1$ and $2$: "[]()", then "()" is left. After that you can erase it whole. You could erase the whole string from the beginning but you would get one move instead of two.

In the third example you can first erase the brackets on positions $1$ and $3$: "([)]". They form an RBS "()". Then "[]" is left, so you can erase it whole.

In the fourth example there is no subsequence that is an RBS, so you can't perform a move at all.

In the fifth example you can erase the brackets on positions $2$ and $4$: ")[(]" and get ")(" as a result. You can erase nothing from it.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	s = input()
	zso = kso = sum = 0
	for i in range(len(s)):
		if s[i] == '(':
			zso += 1
		elif s[i] == '[':
			kso += 1
		elif s[i] == ')' and zso > 0:
			zso -= 1
			sum += 1
		elif s[i] == ']' and kso > 0:
			kso -= 1
			sum += 1
	print(sum)


t = int(input())

def count(s, b, e):
	res = 0
	st = 0
	for i in range(len(s)):
		if s[i] == b:
			st += 1
		if s[i] == e:
			if st > 0:
				res += 1
				st -= 1
	return res
for _ in range(t):
	s = input()
	print(count(s, '(', ')') + count(s, '[', ']'))


def solve(str, key):
	res = 0
	l = 0
	for i in str:
		if i == key[0]:
			l += 1
		elif i == key[1] and l > 0:
			res += 1
			l -= 1
	return res
c = int(input())
while c > 0:
	str = input()
	print(solve(str, '()') + solve(str, '[]'))
	c -= 1


for _ in range(int(input())):
	n = input()
	lx = 0
	ly = 0
	ans = 0
	for i in range(len(n)):
		if n[i] == '(':
			lx += 1
		elif n[i] == ')':
			if lx > 0:
				ans += 1
				lx -= 1
		elif n[i] == '[':
			ly += 1
		elif ly > 0:
			ans += 1
			ly -= 1
	print(ans)


def solve():
	s = input()
	(os, op, cnt) = (0, 0, 0)
	for i in s:
		if i == '(':
			op += 1
		elif i == '[':
			os += 1
		elif i == ')' and op > 0:
			op -= 1
			cnt += 1
		elif i == ']' and os > 0:
			os -= 1
			cnt += 1
	print(cnt)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(a, b, c) = (0, 0, 0)
	for i in input():
		if i == '(':
			a += 1
		elif i == ')':
			(c, a) = (c + (a > 0), max(a - 1, 0))
		elif i == '[':
			b += 1
		elif i == ']':
			(c, b) = (c + (b > 0), max(b - 1, 0))
	print(c)


roundies = ['(', ')']
squaries = ['[', ']']
for i in range(int(input())):
	string = input()
	rounds = [i for i in string if i in roundies]
	squares = [i for i in string if i in squaries]
	(count_rounds, count_round_openers) = (0, 0)
	(count_squares, count_square_openers) = (0, 0)
	for n in rounds:
		if n == '(':
			count_round_openers += 1
		elif count_round_openers >= 1:
			count_rounds += 1
			count_round_openers -= 1
	for x in squares:
		if x == '[':
			count_square_openers += 1
		elif count_square_openers >= 1:
			count_squares += 1
			count_square_openers -= 1
	print(count_squares + count_rounds)


for i in range(int(input())):
	s = input()
	b1 = 0
	b2 = 0
	ans = 0
	for i in s:
		if i == '(':
			b1 += 1
		elif i == '[':
			b2 += 1
		elif i == ')':
			if b1:
				b1 -= 1
				ans += 1
		elif i == ']':
			if b2:
				b2 -= 1
				ans += 1
	print(ans)


def delkv(str):
	if str != '' and str[0] == ']':
		while str != '' and str[0] == ']':
			str = str[1:]
		return str
	else:
		return str

def delkr(str):
	if str != '' and str[0] == ')':
		while str != '' and str[0] == ')':
			str = str[1:]
		return str
	else:
		return str
n = int(input())
for i in range(n):
	str = input()
	kv = 0
	kr = 0
	kol = 0
	for el in str:
		if el == '(':
			kr += 1
		if el == ')' and kr > 0:
			kr -= 1
			kol += 1
		if el == '[':
			kv += 1
		if el == ']' and kv > 0:
			kv -= 1
			kol += 1
	print(kol)


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


for i in range(int(input())):
	s = input()
	x = 0
	y = 0
	z = 0
	for i in s:
		if i == '[':
			y = y + 1
		elif i == '(':
			x = x + 1
		elif i == ']' and y > 0:
			z += 1
			y -= 1
		elif i == ')' and x > 0:
			z += 1
			x -= 1
	print(z)


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
t = int(input())
for tt in range(t):
	s = input()
	ans = 0
	a = 0
	b = 0
	for i in s:
		if i == '(' or i == ')':
			if i == '(':
				if a < 0:
					a = 1
				else:
					a += 1
			else:
				if a >= 1:
					ans += 1
				a -= 1
		elif i == '[':
			if b < 0:
				b = 1
			else:
				b += 1
		else:
			if b >= 1:
				ans += 1
			b -= 1
	print(ans)


for _ in range(int(input())):
	s = input()
	c1 = 0
	c2 = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == '(':
			c1 += 1
		elif s[i] == '[':
			c2 += 1
		elif s[i] == ')' and c1 > 0:
			ans += 1
			c1 -= 1
		elif s[i] == ']' and c2 > 0:
			ans += 1
			c2 -= 1
	print(ans)


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
t = ini()
for _ in range(t):
	s = ins()
	ans = 0
	count = 0
	for i in s:
		if i == '(':
			count += 1
		if i == ')':
			if count > 0:
				ans += 1
				count -= 1
	count = 0
	for i in s:
		if i == '[':
			count += 1
		if i == ']':
			if count > 0:
				ans += 1
				count -= 1
	print(ans)


def solve():
	s = input()
	cnt = 0
	fo = []
	so = []
	for i in range(len(s)):
		if s[i] == '(':
			fo.append(s[i])
		elif s[i] == '[':
			so.append(s[i])
		elif s[i] == ')':
			if len(fo) > 0:
				fo.pop()
				cnt += 1
		elif s[i] == ']':
			if len(so) > 0:
				so.pop()
				cnt += 1
	return cnt
t = int(input())
for i in range(t):
	print(solve())


t = int(input())
while t:
	st = input()
	(s, r, nr, ns) = (0, 0, 0, 0)
	for i in st:
		if i == '[':
			s += 1
		if i == '(':
			r += 1
		if i == ']' and s > 0:
			ns += 1
			s -= 1
		if i == ')' and r > 0:
			nr += 1
			r -= 1
	print(nr + ns)
	t -= 1


def solve(line):
	totalCount = 0
	(cnt1, cnt2) = (0, 0)
	for ch in line:
		if ch == '(':
			cnt1 += 1
		elif ch == '[':
			cnt2 += 1
		elif ch == ')' and cnt1 >= 1:
			cnt1 -= 1
			totalCount += 1
		elif ch == ']' and cnt2 >= 1:
			cnt2 -= 1
			totalCount += 1
	return totalCount
n = int(input())
for _ in range(n):
	print(solve(input()))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	s = input()
	a1 = 0
	a2 = 0
	b1 = 0
	b2 = 0
	r = 0
	for i in s:
		if i == '(':
			a1 += 1
		elif i == '[':
			b1 += 1
		elif i == ')':
			a2 += 1
			if a2 <= a1:
				r += 1
			else:
				a2 -= 1
		elif i == ']':
			b2 += 1
			if b2 <= b1:
				r += 1
			else:
				b2 -= 1
	print(r)


import sys
from collections import Counter, defaultdict as ddict
from pprint import pprint
from functools import lru_cache
from heapq import *
from itertools import zip_longest
from string import *
cache = lru_cache(None)
rl = lambda : next(sys.stdin, '').rstrip('\n')
ri = lambda : int(rl())
rfs = lambda : rl().split()
ris = lambda : list(map(int, rfs()))
rds = lambda : list(map(float, rfs()))
t = ri()
for _ in range(t):
	s = rl()
	par = bra = ans = 0
	for c in s:
		if c == '(':
			par += 1
		elif c == '[':
			bra += 1
		elif c == ')':
			ans += par > 0
			par -= par > 0
		elif c == ']':
			ans += bra > 0
			bra -= bra > 0
	print(ans)


for _ in range(int(input())):
	s = input()
	z = 0
	x = 0
	flg = 0
	for i in s:
		if i == '(':
			z += 1
		if i == '[':
			x += 1
		if i == ')':
			if z > 0:
				z -= 1
				flg += 1
		if i == ']':
			if x > 0:
				x -= 1
				flg += 1
	print(flg)


def solve(st):
	(a, b, ans) = (0, 0, 0)
	for it in st:
		if it == '(':
			a += 1
		elif it == ')':
			if a > 0:
				(ans, a) = (ans + 1, a - 1)
		elif it == '[':
			b += 1
		elif b > 0:
			(ans, b) = (ans + 1, b - 1)
	return ans
for case in range(int(input())):
	st = input()
	ans = solve(st)
	print(ans)


read = lambda : map(int, input().split())
T = int(input())
for t in range(T):
	s = input()
	(c1, c2, ans) = (0, 0, 0)
	for c in s:
		if c == '(':
			c1 += 1
		if c == ')' and c1:
			c1 -= 1
			ans += 1
		if c == '[':
			c2 += 1
		if c == ']' and c2:
			c2 -= 1
			ans += 1
	print(ans)


def mp():
	return map(int, input().split())

def i():
	return int(input())
n = i()
for i in range(n):
	s = input()
	v = []
	(a, b) = (0, 0)
	ans = 0
	for i in s:
		if i == '(' or i == '[':
			if i == '(':
				a += 1
			else:
				b += 1
		elif a > 0 and i == ')':
			ans += 1
			a -= 1
		elif b > 0 and i == ']':
			ans += 1
			b -= 1
	print(ans)


for i in range(int(input())):
	s = input()
	c1 = 0
	c2 = 0
	c = 0
	for i in s:
		if i == '(':
			c1 += 1
		elif i == '[':
			c2 += 1
		elif i == ')' and c1 > 0:
			c1 -= 1
			c += 1
		elif i == ']' and c2 > 0:
			c2 -= 1
			c += 1
	print(c)


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


for _ in range(int(input())):
	s = input()
	temp = set()
	a_open = 0
	b_open = 0
	ans = 0
	for i in s:
		if i == '[':
			a_open += 1
		elif i == '(':
			b_open += 1
		elif i == ']':
			if a_open:
				a_open -= 1
				ans += 1
		elif i == ')':
			if b_open:
				b_open -= 1
				ans += 1
	print(ans)


def RBS(sequence):
	leftCurveBracket = []
	leftSquareBracket = []
	c = 0
	for i in sequence:
		if i == '(':
			leftCurveBracket.append(i)
		elif i == ')':
			if len(leftCurveBracket) != 0:
				leftCurveBracket.pop()
				c += 1
		elif i == '[':
			leftSquareBracket.append(i)
		elif i == ']':
			if len(leftSquareBracket) != 0:
				leftSquareBracket.pop()
				c += 1
	return c
t = int(input())
for _ in range(t):
	a = input()
	sequence = list(a)
	print(RBS(sequence))


def get_nums():
	return [int(x) for x in input().split()]

def solve(S):
	ans = PA = SQ = 0
	for c in S:
		if c == '(':
			PA += 1
		elif c == '[':
			SQ += 1
		elif c == ')':
			if PA:
				ans += 1
				PA -= 1
		elif SQ:
			ans += 1
			SQ -= 1
	return ans
(T,) = get_nums()
for _ in range(T):
	S = input()
	print(solve(S))


t = int(input())

def solve():
	moves = 0
	s = input()
	remb1 = 0
	remb2 = 0
	for i in s:
		if i == '(':
			remb1 += 1
		elif i == ')':
			if remb1 > 0:
				moves += 1
				remb1 -= 1
		elif i == '[':
			remb2 += 1
		elif remb2 > 0:
			moves += 1
			remb2 -= 1
	print(moves)
for i in range(t):
	solve()


for t in range(int(input())):
	s = input()
	a = 0
	b = 0
	ans = 0
	for i in s:
		if i == '(':
			a += 1
		elif i == '[':
			b += 1
		elif i == ')' and a > 0:
			ans += 1
			a -= 1
		elif i == ']' and b > 0:
			ans += 1
			b -= 1
	print(ans)


t = int(input())
for i in range(t):
	a = input()
	c = 0
	k = 0
	d = 0
	for j in a:
		if j == '(':
			k += 1
		elif j == '[':
			d += 1
		elif j == ')' and k > 0:
			c += 1
			k -= 1
		elif j == ']' and d > 0:
			c += 1
			d -= 1
	print(c)


import sys
t = int(input())
for test in range(t):
	s = input()
	a = 0
	b = 0
	res = 0
	for c in s:
		if c == '(':
			a += 1
		elif c == '[':
			b += 1
		elif c == ')' and a > 0:
			a -= 1
			res += 1
		elif c == ']' and b > 0:
			b -= 1
			res += 1
	print(res)


n_tests = int(input())
for test in range(n_tests):
	brackets = input()
	par = 0
	brac = 0
	total = 0
	for bracket in brackets:
		if bracket == '(':
			par += 1
			continue
		elif bracket == '[':
			brac += 1
			continue
		elif bracket == ')' and par > 0:
			total += 1
			par -= 1
			continue
		elif bracket == ']' and brac > 0:
			total += 1
			brac -= 1
			continue
	print(total)


def print_hi(s):
	(L1, R1, L2, R2, count) = (0, 0, 0, 0, 0)
	for i in s:
		if i == ')' and L1 != 0:
			L1 = L1 - 1
			count = count + 1
		elif i == ']' and L2 != 0:
			L2 = L2 - 1
			count = count + 1
		elif i == '(':
			L1 = L1 + 1
		elif i == '[':
			L2 = L2 + 1
	return count
for _ in range(int(input())):
	str = input()
	print(print_hi(str))


import sys
import os
from io import BytesIO, IOBase
from math import inf
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	(a, b, ans) = (0, 0, 0)
	s = input()
	for ch in s:
		if ch == '(':
			a += 1
		if ch == ')':
			if a:
				a -= 1
				ans += 1
		if ch == '[':
			b += 1
		if ch == ']':
			if b:
				b -= 1
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	a = input()
	count1 = 0
	count2 = 0
	ans = 0
	for i in range(len(a)):
		if a[i] == '(':
			count1 = count1 + 1
		elif a[i] == '[':
			count2 = count2 + 1
		elif a[i] == ')':
			if count1 != 0:
				ans = ans + 1
				count1 = count1 - 1
			else:
				pass
		elif a[i] == ']':
			if count2 != 0:
				ans = ans + 1
				count2 = count2 - 1
			else:
				pass
	print(ans)


for i in range(int(input())):
	s = input()
	cnt = 0
	cnt2 = 0
	ans = 0
	for i in s:
		if i == '(':
			cnt += 1
		elif i == '[':
			cnt2 += 1
		elif i == ')' and cnt > 0:
			ans += 1
			cnt -= 1
		elif i == ']' and cnt2 > 0:
			ans += 1
			cnt2 -= 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	(res, round, square) = (0, 0, 0)
	for c in s:
		round += c == '('
		square += c == '['
		if c == ')' and round > 0:
			round -= 1
			res += 1
		if c == ']' and square > 0:
			square -= 1
			res += 1
	print(res)


for tt in range(int(input())):
	s = input()
	ans = 0
	(a1, a2) = (0, 0)
	for c in s:
		if c == '(':
			a1 += 1
		elif c == '[':
			a2 += 1
		elif c == ')':
			ans += a1 > 0
			a1 = max(a1 - 1, 0)
		else:
			ans += a2 > 0
			a2 = max(a2 - 1, 0)
	print(ans)


def fun(st):
	ob = '('
	cb = ')'
	osb = '['
	csb = ']'
	ls = []
	count = 0
	count_ob = 0
	count_sob = 0
	for i in st:
		if i == ob or i == osb:
			if i == ob:
				count_ob += 1
			else:
				count_sob += 1
		else:
			if i == cb:
				if count_ob > 0:
					count_ob -= 1
					count += 1
			if i == csb:
				if count_sob > 0:
					count_sob -= 1
					count += 1
	print(count)
T = int(input())
for i in range(T):
	t = input()
	fun(t)


from sys import stdin, stdout
t = int(input())
for _ in range(t):
	s = input()
	ans = 0
	a = 0
	b = 0
	for i in s:
		if i == '(' or i == '[':
			if i == '(':
				a += 1
			else:
				b += 1
		elif i == ')':
			if a > 0:
				a -= 1
				ans += 1
		elif b > 0:
			b -= 1
			ans += 1
	print(ans)


def ct(l, c):
	res = 0
	stack = 0
	for i in l:
		if i == c:
			stack += 1
		elif stack > 0:
			stack -= 1
			res += 1
	return res
for _ in range(int(input())):
	s = input()
	rb = []
	sb = []
	for i in s:
		if i == '(' or i == ')':
			rb.append(i)
		else:
			sb.append(i)
	print(ct(rb, '(') + ct(sb, '['))


for _ in range(int(input())):
	s = input()
	x = s
	y = s
	x = x.replace('[', '')
	x = x.replace(']', '')
	y = y.replace('(', '')
	y = y.replace(')', '')
	stack = []
	count = 0
	for i in x:
		if stack:
			if stack[-1] == '(' and i == ')':
				count += 1
				stack.pop()
			else:
				stack.append(i)
		else:
			stack.append(i)
	stack1 = []
	count1 = 0
	for i in y:
		if stack1:
			if stack1[-1] == '[' and i == ']':
				count1 += 1
				stack1.pop()
			else:
				stack1.append(i)
		else:
			stack1.append(i)
	print(count1 + count)


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


t = int(input())
for _ in range(t):
	s = input().strip()
	curr0 = 0
	num0 = 0
	curr1 = 0
	num1 = 0
	for y in s:
		if y == '(':
			curr0 += 1
		elif y == '[':
			curr1 += 1
		elif y == ')':
			if curr0 > 0:
				curr0 -= 1
				num0 += 1
		elif curr1 > 0:
			curr1 -= 1
			num1 += 1
	print(num0 + num1)


for _ in range(int(input())):
	s = input()
	max = [0, 0]
	count = {'(': 0, '[': 0}
	for i in s:
		if i == '(':
			count['('] += 1
		elif i == ')' and count['('] >= 1:
			count['('] -= 1
			max[0] += 1
		elif i == '[':
			count['['] += 1
		elif i == ']' and count['['] >= 1:
			count['['] -= 1
			max[1] += 1
	print(max[0] + max[1])


t = int(input())
for j in range(t):
	s = input()
	cnt = 0
	pnt = 0
	aj = 0
	for i in s:
		if i == '[':
			cnt += 1
		elif i == ']':
			if cnt > 0:
				cnt -= 1
				aj += 1
		elif i == '(':
			pnt += 1
		elif i == ')':
			if pnt > 0:
				pnt -= 1
				aj += 1
	print(aj)


for _ in range(int(input())):
	string = input()
	ans = 0
	f = 0
	g = 0
	for i in range(len(string)):
		if string[i] == '[':
			f += 1
		elif string[i] == ']':
			if f > 0:
				ans += 1
				f -= 1
		elif string[i] == '(':
			g += 1
		elif string[i] == ')':
			if g > 0:
				ans += 1
				g -= 1
	print(ans)


for u in range(int(input())):
	x = input()
	l = []
	ans = 0
	for i in range(len(x)):
		if x[i] == '(':
			l.append(x[i])
		elif x[i] == ')':
			if len(l) == 0:
				continue
			else:
				ans += 1
				l.pop()
	s = []
	for i in range(len(x)):
		if x[i] == '[':
			s.append(x[i])
		elif x[i] == ']':
			if len(s) == 0:
				continue
			else:
				ans += 1
				s.pop()
	print(ans)


t = int(input())
for count1 in range(t):
	s = input()
	result = 0
	aux1 = 0
	aux2 = 0
	for count2 in range(len(s)):
		if s[count2] == '(':
			aux1 = aux1 + 1
		elif s[count2] == '[':
			aux2 = aux2 + 1
		elif s[count2] == ')':
			if aux1:
				aux1 = aux1 - 1
				result = result + 1
		elif s[count2] == ']':
			if aux2:
				aux2 = aux2 - 1
				result = result + 1
	print(result)


from sys import stdin, stdout

def hi(s, x, y):
	(a, b) = (0, 0)
	for c in s:
		if c == y:
			if a > 0:
				a -= 1
				b += 1
		elif c == x:
			a += 1
	return b
for _ in range(int(input())):
	s = input()
	print(hi(s, '(', ')') + hi(s, '[', ']'))


def calculate(string, bracketOne, bracketTwo):
	bal = 0
	count = 0
	for char in string:
		if char == bracketTwo:
			if bal > 0:
				bal -= 1
				count += 1
		elif char == bracketOne:
			bal += 1
	return count
num = int(input())
for i in range(num):
	string = input()
	print(calculate(string, '(', ')') + calculate(string, '[', ']'))


def solve(bracket):
	round_bracket = square_bracket = total_rbs = 0
	for i in range(0, len(bracket)):
		if bracket[i] == '(':
			round_bracket += 1
		elif bracket[i] == '[':
			square_bracket += 1
		elif bracket[i] == ')':
			if round_bracket > 0:
				total_rbs += 1
				round_bracket -= 1
		elif bracket[i] == ']':
			if square_bracket > 0:
				total_rbs += 1
				square_bracket -= 1
	return total_rbs
t = int(input())
for _ in range(0, t):
	bracket = input()
	print(solve(bracket))


n = int(input())
for i in range(n):
	str1 = input()
	l = len(str1)
	os = 0
	ot = 0
	cs = 0
	ct = 0
	e = 0
	for j in range(l):
		if str1[j] == '(':
			os = os + 1
		elif str1[j] == '[':
			ot = ot + 1
		elif str1[j] == ')' and os >= 1:
			os = os - 1
			e = e + 1
		elif str1[j] == ']' and ot >= 1:
			ot = ot - 1
			e = e + 1
	print(e)


for _ in range(int(input())):
	s = input()
	(d, a) = ({'(': 0, '[': 0}, 0)
	for i in s:
		if i in d:
			d[i] += 1
		elif i == ')':
			if d['('] > 0:
				a += 1
				d['('] -= 1
		elif i == ']':
			if d['['] > 0:
				a += 1
				d['['] -= 1
	print(a)


for _ in range(int(input())):
	s = input()
	(ofb, cfb, otb, ctb) = (0, 0, 0, 0)
	for i in s:
		if i == '(':
			ofb += 1
		if i == ')':
			if not ofb == cfb:
				cfb += 1
		if i == '[':
			otb += 1
		if i == ']':
			if not otb == ctb:
				ctb += 1
	print(cfb + ctb)


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
	s = ins()
	st1 = []
	st2 = []
	ans = 0
	for i in s:
		if i == '(':
			st1.append(i)
		elif i == ')' and len(st1):
			ans += 1
			st1.pop()
		elif i == '[':
			st2.append(i)
		elif i == ']' and len(st2):
			ans += 1
			st2.pop()
	print(ans)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


T = int(input())
for tc in range(T):
	s = list(input())
	(a1, a2) = (0, 0)
	m = 0
	for c in s:
		if c == '(':
			a1 += 1
		if c == '[':
			a2 += 1
		if c == ')':
			if a1 > 0:
				a1 -= 1
				m += 1
		if c == ']':
			if a2 > 0:
				a2 -= 1
				m += 1
	print(m)


import math
for _ in range(int(input())):
	ar = list(input())
	(o1, o2, c1, c2) = (0, 0, 0, 0)
	count = 0
	for i in ar:
		if i == '[':
			o1 += 1
		elif i == ']' and o1 > 0:
			count += 1
			o1 -= 1
	for i in ar:
		if i == '(':
			o2 += 1
		elif i == ')' and o2 > 0:
			count += 1
			o2 -= 1
	print(count)


import sys, collections, math, itertools, random
INF = sys.maxsize

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
for _ in range(int(input())):
	s = input()
	sq = 0
	cnt = 0
	for i in range(len(s)):
		if s[i] == '[':
			sq += 1
		if s[i] == ']':
			if sq:
				cnt += 1
				sq -= 1
	sq = 0
	for i in range(len(s)):
		if s[i] == '(':
			sq += 1
		if s[i] == ')':
			if sq:
				cnt += 1
				sq -= 1
	print(cnt)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from collections import deque as dq
for _ in range(N()):
	s = input().strip()
	c = 0
	ro = 0
	sq = 0
	i = 0
	while i < len(s):
		if s[i] == '(':
			ro += 1
		elif s[i] == '[':
			sq += 1
		elif s[i] == ')' and ro:
			ro -= 1
			c += 1
		elif s[i] == ']' and sq:
			sq -= 1
			c += 1
		i += 1
	print(c)


loopcount = int(input())
for loop in range(loopcount):
	x = input()
	fs = 0
	ts = 0
	output = 0
	for i in x:
		if i == '(':
			fs += 1
		elif i == '[':
			ts += 1
		elif fs > 0 and i == ')':
			fs -= 1
			output += 1
		elif ts > 0 and i == ']':
			ts -= 1
			output += 1
	print(output)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
for _ in range(L()[0]):
	s = input()
	R = []
	S = []
	for c in s:
		if c in ['(', ')']:
			R.append(c)
		else:
			S.append(c)
	a = 0
	b = 0
	stk = []
	for c in R:
		if c == '(':
			stk.append(c)
		elif stk:
			stk.pop()
			a += 1
	stk = []
	for c in S:
		if c == '[':
			stk.append(c)
		elif stk:
			stk.pop()
			b += 1
	print(a + b)
endtime = time.time()


for _ in range(int(input())):
	s = input()
	p1 = []
	p2 = -1
	q1 = []
	q2 = -1
	an = 0
	for i in range(len(s)):
		if s[i] == '[':
			p1.append(s[i])
		if s[i] == ']':
			if p1 != []:
				an += 1
				p1.pop()
		if s[i] == '(':
			q1.append('(')
		if s[i] == ')':
			if q1 != []:
				an += 1
				q1.pop()
	print(an)


rn = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rns = lambda : map(int, input().split())
rs = lambda : input()
yn = lambda x: print('Yes') if x else print('No')
YN = lambda x: print('YES') if x else print('NO')
for _ in range(rn()):
	s = rs()
	ans = 0
	b = 0
	for i in s:
		if i == '(':
			b += 1
		elif i == ')':
			if b > 0:
				ans += 1
				b -= 1
	b = 0
	for i in s:
		if i == '[':
			b += 1
		elif i == ']':
			if b > 0:
				ans += 1
				b -= 1
	print(ans)


import math
import string
import random
from random import randrange
from collections import deque
from collections import defaultdict
t = int(input())
while t > 0:
	t -= 1
	s = input().strip()
	stk = {'(': 0, '[': 0}
	ans = 0
	for i in range(len(s)):
		if s[i] == '(' or s[i] == '[':
			stk[s[i]] += 1
		elif len(stk) > 0:
			if s[i] == ')':
				if stk['('] > 0:
					stk['('] -= 1
					ans += 1
			elif stk['['] > 0:
				stk['['] -= 1
				ans += 1
	print(ans)


def solve(string):
	p_stack = []
	s_stack = []
	res = 0
	for ch in string:
		if ch == '(':
			p_stack.append(1)
		elif len(p_stack) != 0 and ch == ')':
			p_stack.pop()
			res += 1
		if ch == '[':
			s_stack.append(1)
		elif len(s_stack) != 0 and ch == ']':
			s_stack.pop()
			res += 1
	print(res)
for _ in range(int(input())):
	string = input()
	solve(string)


for _ in range(int(input())):
	s = input()
	cbl = 0
	cbr = 0
	sbl = 0
	sbr = 0
	c = 0
	for i in s:
		if i == '(':
			cbl += 1
		elif i == '[':
			sbl += 1
		elif i == ')':
			if cbl > 0:
				cbl -= 1
				c += 1
		elif i == ']':
			if sbl > 0:
				sbl -= 1
				c += 1
	print(c)


import sys
n = int(sys.stdin.readline())

def solver(x):
	a = 0
	b = 0
	ret = 0
	for c in x:
		if c == '(':
			a += 1
		elif c == '[':
			b += 1
		if c == ')' and a > 0:
			ret += 1
			a -= 1
		elif c == ']' and b > 0:
			ret += 1
			b -= 1
	return ret
for _ in range(n):
	print(solver(sys.stdin.readline().rstrip()))


import sys
import math
t = int(input())
for w in range(t):
	s = input()
	c = 0
	(op1, op2) = (0, 0)
	(cl1, cl2) = (0, 0)
	for i in s:
		if i == '(':
			op1 += 1
		elif i == '[':
			op2 += 1
		elif i == ')':
			if op1 > 0:
				op1 -= 1
				cl1 += 1
		elif op2 > 0:
			op2 -= 1
			cl2 += 1
	print(cl1 + cl2)


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def main():
	t = int(input())
	while t:
		s = input()
		(has_square, has_round) = (0, 0)
		(valid_square, valid_round) = (0, 0)
		for c in s:
			if c == '(':
				has_round += 1
			elif c == ')':
				if has_round > 0:
					has_round -= 1
					valid_round += 1
			elif c == '[':
				has_square += 1
			elif c == ']':
				if has_square > 0:
					has_square -= 1
					valid_square += 1
		print(str(valid_square + valid_round))
		t -= 1
main()


t = int(input())
for i in range(t):
	s = input()
	ans = 0
	o_s_b = 0
	o_c_b = 0
	for i in s:
		if i == '[':
			o_s_b += 1
		elif i == '(':
			o_c_b += 1
		elif i == ']' and o_s_b > 0:
			ans += 1
			o_s_b -= 1
		elif i == ')' and o_c_b > 0:
			ans += 1
			o_c_b -= 1
	print(ans)


for i in range(int(input())):
	s = list(input())
	z = 0
	v = 0
	g = 0
	c = 0
	for i in range(len(s)):
		if s[i] == '(':
			z += 1
		elif s[i] == ')':
			z -= 1
			if z >= 0:
				v += 1
			else:
				z = 0
		if s[i] == '[':
			g += 1
		elif s[i] == ']':
			g -= 1
			if g >= 0:
				c += 1
			else:
				g = 0
	print(v + c)


a = input()
for x in range(int(a)):
	d = input()
	ans = 0
	tag = []
	tag1 = []
	for i in d:
		if i == ']' and len(tag) > 0:
			ans += 1
			tag.pop()
		elif i == ')' and len(tag1) > 0:
			ans += 1
			tag1.pop()
		elif i == '(':
			tag1.append('(')
		elif i == '[':
			tag.append('[')
	print(ans)


for _ in range(int(input())):
	s = input()
	res = [0, 0]
	(c1, c2) = (0, 0)
	for i in s:
		if i == '(':
			res[0] += 1
		elif i == '[':
			res[1] += 1
		elif i == ')':
			if res[0] != 0:
				res[0] -= 1
				c1 += 1
		elif res[1] != 0:
			res[1] -= 1
			c2 += 1
	print(c1 + c2)


f = int(input())
for q in range(f):
	n = input()
	k = 0
	g = 0
	a = 0
	for i in range(len(n)):
		if n[i] == '(':
			k += 1
		if n[i] == ')' and k > 0:
			a += 1
			k -= 1
		if n[i] == '[':
			g += 1
		if n[i] == ']' and g > 0:
			a += 1
			g -= 1
	print(a)


def read_ints():
	return map(int, input().split())

def f(s, char_a, char_b):
	result = 0
	a_n = 0
	for char in s:
		if char == char_a:
			a_n += 1
		elif char == char_b:
			if a_n > 0:
				a_n -= 1
				result += 1
	return result
t = int(input())
for i_t in range(t):
	s = input()
	result = f(s, '(', ')') + f(s, '[', ']')
	print(result)


def calc(s, x, y):
	(bal, cnt) = (0, 0)
	for c in s:
		if c == y:
			if bal > 0:
				bal -= 1
				cnt += 1
		elif c == x:
			bal += 1
	return cnt
for _ in range(int(input())):
	s = input()
	print(calc(s, '(', ')') + calc(s, '[', ']'))


for i in range(int(input())):
	st = input()
	c1 = 0
	c2 = 0
	move = 0
	for j in st:
		if j == '(':
			c1 += 1
		elif j == '[':
			c2 += 1
		elif j == ')' and c1 > 0:
			c1 -= 1
			move += 1
		elif j == ']' and c2 > 0:
			c2 -= 1
			move += 1
	print(move)


for _ in range(int(input())):
	(n, lst, ans) = (list(input()), [0, 0], 0)
	for i in n:
		if i == '(':
			lst[0] += 1
		elif i == '[':
			lst[1] += 1
		if i == ')' and lst[0] > 0:
			lst[0] -= 1
			ans += 1
		elif i == ']' and lst[1] > 0:
			lst[1] -= 1
			ans += 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	s = str(input())
	buffer_1 = 0
	buffer_2 = 0
	answer = 0
	for i in range(len(s)):
		r = s[i]
		if r == '(' or r == '[':
			if r == '(':
				buffer_1 += 1
			else:
				buffer_2 += 1
		elif r == ')':
			if buffer_1 > 0:
				buffer_1 -= 1
				answer += 1
		elif buffer_2 > 0:
			buffer_2 -= 1
			answer += 1
	print(answer)


tc = int(input())
for _ in range(tc):
	s = input()
	cnt = 0
	stack_of_1 = [0, 0]
	stack_of_2 = [0, 0]
	for i in s:
		if i == '(':
			stack_of_1[0] += 1
		elif i == ')':
			stack_of_1[1] -= 1
			if stack_of_1[0] + stack_of_1[1] >= 0:
				cnt += 1
			else:
				stack_of_1[0] = 0
				stack_of_1[1] = 0
		elif i == '[':
			stack_of_2[0] += 1
		elif i == ']':
			stack_of_2[1] -= 1
			if stack_of_2[0] + stack_of_2[1] >= 0:
				cnt += 1
			else:
				stack_of_2[0] = 0
				stack_of_2[1] = 0
	print(cnt)


class Solution:

	def __init__(self):
		self.travelled_city = dict()

	def twobrackets(self, st):
		p_stack = []
		q_stack = []
		count = 0
		for e in st:
			if e == '[':
				p_stack.append(1)
			elif len(p_stack) != 0 and e == ']':
				p_stack.pop()
				count += 1
			if e == '(':
				q_stack.append(1)
			elif len(q_stack) != 0 and e == ')':
				q_stack.pop()
				count += 1
		return count
cases = int(input())
while cases:
	sol = Solution()
	st = input()
	steps = sol.twobrackets(st)
	print(steps)
	cases -= 1


cases = int(input())
while cases:
	cases -= 1
	s = input()
	(op1, cl1, op2, cl2) = (0, 0, 0, 0)
	ans = 0
	for let in s:
		if let == '[':
			op1 += 1
		elif let == ']':
			if op1 > 0:
				ans += 1
				op1 -= 1
		elif let == '(':
			op2 += 1
		elif let == ')':
			if op2 > 0:
				ans += 1
				op2 -= 1
	print(ans)


import os
from sys import stdin, stdout

def solve(tc):
	s = stdin.readline().strip()
	n = len(s)
	cnt = 0
	br = [0, 0]
	for i in range(n):
		if s[i] == '(':
			br[0] += 1
		elif s[i] == '[':
			br[1] += 1
		elif s[i] == ')':
			if br[0] > 0:
				cnt += 1
				br[0] -= 1
		elif br[1] > 0:
			cnt += 1
			br[1] -= 1
	print(cnt)
tcs = 1
tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


from math import *
from cmath import *
from itertools import *
from decimal import *
from fractions import *
from sys import *
for x in range(int(input())):
	s = input()
	ans = a = b = 0
	for x in s:
		a += int(x == '(')
		b += int(x == '[')
		if a > 0 and x == ')':
			ans += 1
			a -= 1
		if b > 0 and x == ']':
			ans += 1
			b -= 1
	print(ans)


def solve():
	s = input()
	q = 0
	w = 0
	ans = 0
	for c in s:
		if c == '(':
			q += 1
		if c == ')':
			if q > 0:
				q -= 1
				ans += 1
		if c == '[':
			w += 1
		if c == ']':
			if w > 0:
				w -= 1
				ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def solve(s):
	open = 0
	ans = 0
	for i in s:
		if i == '(':
			open += 1
		elif i == ')':
			if open > 0:
				open -= 1
				ans += 1
	open = 0
	for i in s:
		if i == '[':
			open += 1
		elif i == ']':
			if open > 0:
				open -= 1
				ans += 1
	print(ans)
for _ in range(int(input())):
	solve(input())


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


for _ in range(int(input())):
	arr = list(input())
	n = len(arr)
	roundC = 0
	squareC = 0
	ans = 0
	for i in range(n):
		if arr[i] == '(':
			roundC += 1
		if arr[i] == ')':
			if roundC:
				ans += 1
				roundC -= 1
		if arr[i] == '[':
			squareC += 1
		if arr[i] == ']':
			if squareC:
				ans += 1
				squareC -= 1
	print(ans)


import sys
import os
import math
import copy
from bisect import bisect
from io import BytesIO, IOBase
from math import sqrt, floor, factorial, gcd, log, ceil
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations, accumulate

def Int():
	return int(sys.stdin.readline())

def Mint():
	return map(int, sys.stdin.readline().split())

def Lstr():
	return list(sys.stdin.readline().strip())

def Str():
	return sys.stdin.readline().strip()

def Mstr():
	return map(str, sys.stdin.readline().strip().split())

def List():
	return list(map(int, sys.stdin.readline().split()))

def Hash():
	return dict()

def Mod():
	return 1000000007

def Mat2x2(n):
	return [List() for _ in range(n)]

def Lcm(x, y):
	return x * y // gcd(x, y)

def dtob(n):
	return bin(n).replace('0b', '')

def btod(n):
	return int(n, 2)

def watch(x):
	return print(x)

def common(l1, l2):
	return set(l1).intersection(l2)

def Most_frequent(list):
	return max(set(list), key=list.count)

def solution():
	for _ in range(Int()):
		s = Lstr()
		c = 0
		a = []
		b = []
		for i in range(len(s)):
			if s[i] == '(':
				a.append('(')
			elif s[i] == ')' and len(a) > 0:
				a.pop()
				c += 1
			if s[i] == '[':
				b.append('(')
			elif s[i] == ']' and len(b) > 0:
				b.pop()
				c += 1
		print(c)
solution()


for _ in range(int(input())):
	s = input()
	(bra, par, res) = [0] * 3
	for i in s:
		if i == '[':
			bra += 1
		elif i == '(':
			par += 1
		elif i == ')' and par > 0:
			res += 1
			par -= 1
		elif i == ']' and bra > 0:
			res += 1
			bra -= 1
	print(res)


for i in range(int(input())):
	s = input()
	l = [i for i in s]
	(c, c1, sq) = (0, 0, 0)
	for j in l:
		if j == ')' or j == ']':
			if j == ')' and c1 > 0:
				c = c + 1
				c1 = c1 - 1
			elif j == ']' and sq > 0:
				c = c + 1
				sq = sq - 1
		elif j == '(' or j == '[':
			if j == '(':
				c1 = c1 + 1
			else:
				sq = sq + 1
	print(c)


def manp(s):
	(l0, l1, r0, r1, count) = (0, 0, 0, 0, 0)
	for i in s:
		if i == '[':
			l0 += 1
		elif i == ']' and l0 > 0:
			l0 -= 1
			count += 1
		elif i == '(':
			r0 += 1
		elif i == ')' and r0 > 0:
			r0 -= 1
			count += 1
	return count
for _ in range(int(input())):
	stack = input()
	print(manp(stack))


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	s = minp()
	s1 = 0
	s2 = 0
	res = 0
	for c in s:
		if c == '(':
			s1 += 1
		elif c == ')':
			if s1 > 0:
				s1 -= 1
				res += 1
		elif c == '[':
			s2 += 1
		elif c == ']':
			if s2 > 0:
				s2 -= 1
				res += 1
	print(res)
for i in range(mint()):
	solve()


t = int(input())
for i in range(t):
	s = input()
	n = 0
	a = 0
	b = 0
	for c in s:
		if c == '(':
			a += 1
		if c == '[':
			b += 1
		if c == ')' and a > 0:
			n += 1
			a -= 1
		if c == ']' and b > 0:
			n += 1
			b -= 1
	print(n)


import collections
for _ in range(int(input())):
	s = input()
	l1 = collections.deque()
	l2 = collections.deque()
	l3 = collections.deque()
	l4 = collections.deque()
	for i in range(len(s)):
		if s[i] == '(':
			l1.append(i)
		elif s[i] == ')':
			l2.append(i)
		elif s[i] == '[':
			l3.append(i)
		elif s[i] == ']':
			l4.append(i)
	ss = 0
	while len(l1) > 0 and len(l2) > 0:
		if l1[0] < l2[0]:
			l1.popleft()
			l2.popleft()
			ss += 1
		elif l1[0] > l2[0]:
			while len(l2) > 0 and l1[0] > l2[0]:
				l2.popleft()
	while len(l3) > 0 and len(l4) > 0:
		if l3[0] < l4[0]:
			l3.popleft()
			l4.popleft()
			ss += 1
		elif l3[0] > l4[0]:
			while len(l4) > 0 and l3[0] > l4[0]:
				l4.popleft()
	print(ss)


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


n = int(input())
while n:
	entrada = input()
	temp1 = 0
	temp2 = 0
	resposta = 0
	i = 0
	while i < len(entrada):
		if entrada[i] == '(':
			temp1 += 1
		elif entrada[i] == '[':
			temp2 += 1
		elif entrada[i] == ')':
			if temp1:
				resposta += 1
				temp1 -= 1
		elif entrada[i] == ']':
			if temp2:
				resposta += 1
				temp2 -= 1
		i += 1
	print(resposta)
	n -= 1


import os, sys
if os.environ.get('CODE_ENV', '') != '':
	sys.stdin = open('../input.txt', 'r')
for _ in range(int(input())):
	s = list(input())
	ans = 0
	z = 0
	for x in s:
		z = complex(max(0, z.real), max(0, z.imag))
		if x == '(':
			z += 1
		elif x == ')':
			z -= 1
			if z.real >= 0:
				ans += 1
		elif x == '[':
			z += 1j
		else:
			z -= 1j
			if z.imag >= 0:
				ans += 1
	print(ans)


from sys import stdin
tt = int(stdin.readline())
for loop in range(tt):
	S = stdin.readline()[:-1]
	ans = 0
	x = 0
	y = 0
	for i in S:
		if i == '(':
			x += 1
		elif i == '[':
			y += 1
		elif i == ')':
			if x > 0:
				x -= 1
				ans += 1
		elif y > 0:
			y -= 1
			ans += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	sq = ro = res = 0
	for i in s:
		if i == '(':
			ro += 1
		elif i == '[':
			sq += 1
		elif i == ')':
			if ro > 0:
				res += 1
				ro -= 1
		elif i == ']':
			if sq > 0:
				res += 1
				sq -= 1
	print(res)


def solution(s, x, y):
	(beta, gama) = (0, 0)
	for c in s:
		if c == y:
			if beta > 0:
				beta = beta - 1
				gama = gama + 1
		elif c == x:
			beta = beta + 1
	return gama
for _ in range(int(input())):
	sig = input()
	print(solution(sig, '(', ')') + solution(sig, '[', ']'))


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()

def test():
	s = list(input())
	(b1, b3) = (0, 0)
	r = 0
	for i in s:
		if i == '(':
			b1 += 1
		elif i == '[':
			b3 += 1
		elif i == ')' and b1:
			r += 1
			b1 -= 1
		elif i == ']' and b3:
			r += 1
			b3 -= 1
	return r
t = int(input())
for _ in range(t):
	print(test())


from collections import *
for i1 in range(int(input())):
	s = input()
	n = len(s)
	C = defaultdict(int)
	ans = 0
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			C[s[i]] += 1
		if s[i] == ']':
			C[s[i]] += 1
		if s[i] == '(' and C[')']:
			ans += 1
			C[')'] -= 1
		if s[i] == '[' and C[']']:
			ans += 1
			C[']'] -= 1
	print(ans)


t = int(input())
for j in range(t):
	s = input()
	count = 0
	q1 = 0
	q2 = 0
	for i in range(len(s)):
		if s[i] == '(':
			q1 += 1
		if s[i] == '[':
			q2 += 1
		if s[i] == ')':
			if q1 > 0:
				count += 1
				q1 -= 1
		if s[i] == ']':
			if q2 > 0:
				count += 1
				q2 -= 1
	print(count)


import sys
import math
from bisect import bisect_left
from collections import defaultdict

def get_lcp(s, suffix_array):
	s = s + '$'
	n = len(s)
	lcp = [0] * n
	pos = [0] * n
	for i in range(n - 1):
		pos[suffix_array[i]] = i
	k = 0
	for i in range(n - 1):
		if k > 0:
			k -= 1
		if pos[i] == n - 1:
			lcp[n - 1] = -1
			k = 0
			continue
		else:
			j = suffix_array[pos[i] + 1]
			while max([i + k, j + k]) < n and s[i + k] == s[j + k]:
				k += 1
			lcp[pos[i]] = k
	return lcp

def get_suffix_array(word):
	suffix_array = [('', len(word))]
	for position in range(len(word)):
		sliced = word[len(word) - position - 1:]
		suffix_array.append((sliced, len(word) - position - 1))
	suffix_array.sort(key=lambda x: x[0])
	return [item[1] for item in suffix_array]

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def bin_search(collection, element):
	i = bisect_left(collection, element)
	if i != len(collection) and collection[i] == element:
		return i
	else:
		return -1

def main():
	t = int(input())
	for _ in range(t):
		s = str(input())
		c1 = 0
		c2 = 0
		ans = 0
		for i in range(len(s)):
			if s[i] == '(':
				c1 += 1
			elif s[i] == ')':
				if c1 > 0:
					ans += 1
					c1 -= 1
			elif s[i] == '[':
				c2 += 1
			elif c2 > 0:
				ans += 1
				c2 -= 1
		print(ans)
main()


def solve():
	t = int(input())
	for _ in range(t):
		s = input()
		(leftb1, leftb2) = (0, 0)
		ans = 0
		for x in s:
			if x == '(':
				leftb1 += 1
			elif x == ')':
				if leftb1 > 0:
					ans += 1
					leftb1 -= 1
			elif x == '[':
				leftb2 += 1
			elif x == ']':
				if leftb2 > 0:
					ans += 1
					leftb2 -= 1
		print(ans)
solve()


for _ in range(int(input())):
	s = input()
	(a, b, an) = (0, 0, 0)
	for i in s:
		if i == '(':
			a += 1
		elif i == '[':
			b += 1
		elif i == ')' and a > 0:
			an += 1
			a -= 1
		elif i == ']' and b > 0:
			an += 1
			b -= 1
	print(an)


t = int(input())
for i in range(t):
	s = input()
	sc = 0
	ss = 0
	ct = 0
	for c in s:
		if c == '(':
			sc += 1
		elif c == '[':
			ss += 1
		elif c == ')':
			if sc > 0:
				ct += 1
				sc -= 1
		elif ss > 0:
			ct += 1
			ss -= 1
	print(ct)


for _ in range(int(input())):
	s = input()
	a = []
	b = []
	cnt = 0
	for let in s:
		if let == '(':
			a.append(let)
		elif let == ')':
			if a:
				a.pop()
				cnt += 1
		elif let == '[':
			b.append(let)
		elif b:
			b.pop()
			cnt += 1
	print(cnt)


def solve(s):
	open1 = 0
	open2 = 0
	ans = 0
	for x in s:
		if x == '(':
			open1 += 1
		elif x == '[':
			open2 += 1
		elif x == ')' and open1 > 0:
			ans += 1
			open1 -= 1
		elif x == ']' and open2 > 0:
			ans += 1
			open2 -= 1
	return ans
t = int(input())
while t:
	s = input()
	print(solve(s))
	t -= 1


import io, os, sys
from math import *

def read_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_str():
	return sys.stdin.readline().strip()

def main():
	t = read_ints()[0]
	for _ in range(t):
		s = read_str()
		res = 0
		round = 0
		square = 0
		for c in s:
			if c == '(':
				round += 1
			elif c == '[':
				square += 1
			elif c == ')':
				if round > 0:
					round -= 1
					res += 1
			elif square > 0:
				square -= 1
				res += 1
		print(res)
main()


for _ in range(int(input())):
	t = input()
	(x, y, a) = (0, 0, 0)
	for ch in t:
		if ch == '(':
			x += 1
		if ch == '[':
			y += 1
		if ch == ')' and x:
			a += 1
			x -= 1
		if ch == ']' and y:
			a += 1
			y -= 1
	print(a)


t = int(input())
for i in range(t):
	s = input()
	b1 = 0
	b2 = 0
	ans = 0
	for j in range(len(s)):
		if s[j] == '(':
			b1 += 1
		elif s[j] == '[':
			b2 += 1
		elif s[j] == ')' and b1 > 0:
			b1 -= 1
			ans += 1
		elif s[j] == ']' and b2 > 0:
			b2 -= 1
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	c = []
	c1 = []
	co = 0
	co1 = 0
	flag = 0
	flag1 = 0
	ans = 0
	for j in range(len(s)):
		if s[j] == '(':
			co += 1
		elif s[j] == '[':
			co1 += 1
		elif co and s[j] == ')':
			co -= 1
		elif co1 and s[j] == ']':
			co1 -= 1
	for j in range(len(s)):
		if s[j] == '(':
			flag += 1
		elif s[j] == '[':
			flag1 += 1
	ans += flag - co + (flag1 - co1)
	print(ans)


def check_sign(x, letf, right):
	count = 0
	check = 0
	for i in x:
		if i == right:
			if check > 0:
				check -= 1
				count += 1
		elif i == letf:
			check += 1
	return count
a = int(input())
while a != 0:
	st = str(input())
	print(int(check_sign(st, '(', ')')) + int(check_sign(st, '[', ']')))
	a -= 1


def answer():
	(b1, b2) = (0, 0)
	ans = 0
	for st in s:
		if st == '(':
			b1 += 1
		elif st == ')':
			if b1:
				b1 -= 1
				ans += 1
		elif st == '[':
			b2 += 1
		elif b2:
			b2 -= 1
			ans += 1
	return ans
for T in range(int(input())):
	s = input()
	print(answer())


t = int(input())
for _ in range(t):
	s = list(input())
	c = 0
	p_o = b_o = 0
	for item in s:
		if item == '(':
			p_o += 1
		elif item == '[':
			b_o += 1
		elif item == ')':
			if p_o > 0:
				p_o -= 1
				c += 1
		elif item == ']':
			if b_o > 0:
				b_o -= 1
				c += 1
	print(c)


import sys

def get_single_int():
	return int(sys.stdin.readline().strip())

def get_string():
	return sys.stdin.readline().strip()

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
for i in range(get_single_int()):
	s = get_string()
	available_first = 0
	available_second = 0
	ans = 0
	for j in s:
		if j == '(':
			available_first += 1
		elif j == ')':
			if available_first >= 1:
				available_first -= 1
				ans += 1
			else:
				continue
		elif j == '[':
			available_second += 1
		elif j == ']':
			if available_second >= 1:
				available_second -= 1
				ans += 1
			else:
				continue
	print(ans)


for i in range(int(input())):
	s = input()
	(ans, a, b) = (0, 0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			a += 1
		if s[i] == ')' and a > 0:
			ans += 1
			a = a - 1
		if s[i] == '[':
			b += 1
		if s[i] == ']' and b > 0:
			ans += 1
			b = b - 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	curved = 0
	square = 0
	ans = 0
	for c in s:
		if c == ']':
			if square > 0:
				square -= 1
				ans += 1
		elif c == '[':
			square += 1
		elif c == '(':
			curved += 1
		elif curved > 0:
			curved -= 1
			ans += 1
	print(ans)


n = int(input())
for i in range(n):
	s = input()
	c = 0
	brace = 0
	square = 0
	for j in s:
		if j == '(':
			brace += 1
		elif j == '[':
			square += 1
		elif j == ')' and brace > 0:
			brace -= 1
			c += 1
		elif j == ']' and square > 0:
			square -= 1
			c += 1
	print(c)


import sys

def calcmaxrbs(input):
	result = 0
	cbrackets = []
	sbrackets = []
	for c in input:
		if c == '[':
			sbrackets.append('[')
		elif c == '(':
			cbrackets.append('(')
		elif c == ')':
			if len(cbrackets) != 0:
				cbrackets.pop()
				result = result + 1
		elif c == ']':
			if len(sbrackets) != 0:
				sbrackets.pop()
				result = result + 1
	return result
testcase_flag = True
count = 0
testCaseCount = 0
costs = []
for line in sys.stdin:
	inputs = [x for x in line.strip().split()]
	if testcase_flag:
		testCaseCount = int(inputs[0])
		testcase_flag = False
		continue
	input = inputs[0]
	costs.append(calcmaxrbs(input))
	count = count + 1
	if count == testCaseCount:
		break
for i in range(testCaseCount):
	print(costs[i])


t = int(input())
while t != 0:
	t -= 1
	s = input()
	b1 = 0
	b2 = 0
	ans = 0
	for c in s:
		if c == '(':
			b1 += 1
		elif c == ')':
			if b1 > 0:
				b1 -= 1
				ans += 1
		elif c == '[':
			b2 += 1
		elif c == ']':
			if b2 > 0:
				b2 -= 1
				ans += 1
	print(ans)


import io, os
from math import *
for _ in range(int(input())):
	op = ob = a = 0
	for s in input():
		if s == '(':
			op += 1
		elif s == '[':
			ob += 1
		elif s == ')' and op:
			op -= 1
			a += 1
		elif s == ']' and ob:
			ob -= 1
			a += 1
	print(a)


for _ in range(int(input())):
	string = input()
	max1 = 0
	max2 = 0
	check1 = 0
	check2 = 0
	rs = 0
	for i in string:
		if i == '(':
			check1 += 1
		elif i == ')':
			check1 -= 1
			if check1 < 0:
				check1 = 0
			else:
				max1 += 1
		if i == '[':
			check2 += 1
		elif i == ']':
			check2 -= 1
			if check2 < 0:
				check2 = 0
			else:
				max2 += 1
	rs += max1
	rs += max2
	print(rs)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	(num1, num2, res) = (0, 0, 0)
	for i in range(n):
		if s[i] == '(':
			num1 += 1
		elif s[i] == ')':
			if num1:
				num1 -= 1
				res += 1
		elif s[i] == '[':
			num2 += 1
		elif num2:
			num2 -= 1
			res += 1
	print(res)


t = int(input())
while t:
	s = input()
	count = 0
	r = 0
	u = 0
	for i in s:
		if i == '(':
			r += 1
		elif i == ')':
			if r > 0:
				r -= 1
				count += 1
		if i == '[':
			u += 1
		elif i == ']' and u > 0:
			u -= 1
			count += 1
	print(count)
	t -= 1


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
from itertools import accumulate
import sys
input = sys.stdin.readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	s = st()
	ans = s1 = s2 = 0
	for i in s:
		if i == '(':
			s1 += 1
		elif i == '[':
			s2 += 1
		elif i == ']':
			if s2:
				ans += 1
				s2 -= 1
		elif s1:
			ans += 1
			s1 -= 1
	print(ans)


def twoBrackets(string):
	matched_bracket = 0
	paranthesis = 0
	square = 0
	for val in string:
		if val == '(':
			paranthesis += 1
		elif val == ')' and paranthesis > 0:
			paranthesis -= 1
			matched_bracket += 1
		elif val == '[':
			square += 1
		elif val == ']' and square > 0:
			square -= 1
			matched_bracket += 1
	print(matched_bracket)
testcases = int(input())
while testcases:
	testcases -= 1
	string = input()
	twoBrackets(string)


for i in range(int(input())):
	l = []
	a = input()
	count1 = countrev1 = count2 = countrev2 = 0
	for i in a:
		if i == '(':
			count1 += 1
		elif i == '[':
			count2 += 1
		elif i == ')' and count1 > 0:
			count1 -= 1
			countrev1 += 1
		elif i == ']' and count2 > 0:
			count2 -= 1
			countrev2 += 1
	print(countrev2 + countrev1)


t = int(input())
for _ in range(t):
	s = input()
	cnt1 = 0
	cnt2 = 0
	sum1 = 0
	for i in s:
		if i == '(':
			cnt1 += 1
		elif i == ')':
			if cnt1 > 0:
				cnt1 -= 1
				sum1 += 1
		elif i == '[':
			cnt2 += 1
		elif cnt2 > 0:
			cnt2 -= 1
			sum1 += 1
	print(sum1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	S = list(input())[:-1]
	l1 = 0
	l2 = 0
	res = 0
	for i in range(len(S)):
		if S[i] == '(':
			l1 += 1
		if S[i] == '[':
			l2 += 1
		if S[i] == ')' and l1:
			l1 -= 1
			res += 1
		if S[i] == ']' and l2:
			l2 -= 1
			res += 1
	print(res)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	s = input()
	countsecond1 = 0
	countsecond2 = 0
	countfirst1 = 0
	countfirst2 = 0
	ans = 0
	for i in range(0, len(s)):
		if s[i] == '(':
			countfirst1 += 1
		elif s[i] == '[':
			countsecond1 += 1
		elif s[i] == ')':
			if countfirst1 > 0:
				ans += 1
				countfirst1 -= 1
		elif countsecond1 > 0:
			ans += 1
			countsecond1 -= 1
	print(ans)


for _ in [0] * int(input()):
	s = input()
	d = {'(': 0, '[': 0}
	pairs = 0
	for i in s:
		if i == '(':
			d['('] += 1
		elif i == '[':
			d['['] += 1
		elif i == ')':
			if d['(']:
				pairs += 1
				d['('] -= 1
		elif d['[']:
			pairs += 1
			d['['] -= 1
	print(pairs)


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
for ii in range(int(input())):
	s = input()
	s1 = []
	s2 = []
	ans = 0
	for i in s:
		if i == '(':
			s1.append(1)
		if i == ')':
			if s1:
				s1.pop()
				ans += 1
		if i == '[':
			s2.append(1)
		if i == ']':
			if s2:
				s2.pop()
				ans += 1
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def cnt(c0, c1):
	res = 0
	now = 0
	for c in s:
		if c == c0:
			now += 1
		if c == c1 and now:
			now -= 1
			res += 1
	return res
for _ in range(II()):
	s = SI()
	ans = cnt('(', ')') + cnt('[', ']')
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	r = tr = 0
	ret = 0
	for c in s:
		if c == '(':
			r += 1
		elif c == '[':
			tr += 1
		elif c == ')':
			if r > 0:
				r -= 1
				ret += 1
		elif c == ']':
			if tr > 0:
				tr -= 1
				ret += 1
	print(ret)


def two(string, x, y):
	count = 0
	final = 0
	for i in range(len(string)):
		if string[i] == y:
			if final > 0:
				count = count + 1
				final = final - 1
		elif string[i] == x:
			final = final + 1
	return count
t = int(input())
for i in range(t):
	string = input()
	print(two(string, '(', ')') + two(string, '[', ']'))


for _ in range(int(input())):
	a = input()
	x = []
	y = []
	ans = 0
	for i in a:
		if i == '(':
			x.append(i)
		if i == '[':
			y.append(y)
		if i == ')':
			if len(x) > 0:
				ans += 1
				x.pop()
		if i == ']':
			if len(y) > 0:
				ans += 1
				y.pop()
	print(ans)


def f(s, x, y):
	a = c = 0
	for i in s:
		if i == y:
			if a > 0:
				a -= 1
				c += 1
		if i == x:
			a += 1
	return c
for _ in range(int(input())):
	s = input()
	print(f(s, '(', ')') + f(s, '[', ']'))


t = int(input())
for i in range(t):
	s = input()
	count = 0
	ob = 0
	cb = 0
	op = 0
	cp = 0
	for j in s:
		if j == '(':
			op += 1
		elif j == '[':
			ob += 1
		elif j == ')' and op > cp:
			cp += 1
		elif j == ']' and ob > cb:
			cb += 1
	print(cb + cp)


for _ in range(int(input())):
	a = input()
	cnt1 = cnt2 = ans = 0
	for i in a:
		if i == '(':
			cnt1 += 1
		elif i == '[':
			cnt2 += 1
		elif i == ')' and cnt1 > 0:
			cnt1 -= 1
			ans += 1
		elif i == ']' and cnt2 > 0:
			cnt2 -= 1
			ans += 1
	print(ans)


def countBrackets(s, bracket1, bracket2):
	a = 0
	b = 0
	for i in s:
		if i == bracket1:
			a += 1
		elif i == bracket2 and a > b:
			b += 1
	return b
t = int(input())
for i in range(t):
	s = input()
	result = countBrackets(s, '(', ')') + countBrackets(s, '[', ']')
	print(result)


import sys

def input():
	return sys.stdin.readline()
TestCase = int(input())
for _ in range(TestCase):
	s = input()
	first = []
	max_first = 0
	first_pop = 0
	third = []
	max_third = 0
	third_pop = 0
	for ch in s:
		if ch == '(':
			first.append(ch)
		elif ch == ')':
			if len(first):
				first.pop()
				first_pop += 1
		max_first = max(max_first, first_pop)
	for ch in s:
		if ch == '[':
			third.append(ch)
		elif ch == ']':
			if len(third):
				third.pop()
				third_pop += 1
		max_third = max(max_third, third_pop)
	print(max_first + max_third)


for _ in range(int(input())):
	ans = 0
	s = input()
	b1 = b2 = 0
	for i in range(len(s)):
		if s[i] == '(':
			b1 += 1
		elif s[i] == ')':
			if b1 <= 0:
				continue
			b1 -= 1
			ans += 1
		elif s[i] == '[':
			b2 += 1
		elif s[i] == ']':
			if b2 <= 0:
				continue
			b2 -= 1
			ans += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	curly = square = cnt = 0
	for i in s:
		if i == '(':
			curly += 1
		elif i == ')':
			if curly > 0:
				curly -= 1
				cnt += 1
		elif i == '[':
			square += 1
		elif square > 0:
			square -= 1
			cnt += 1
	print(cnt)


import sys
t = int(sys.stdin.readline().strip())
for j in range(t):
	s = sys.stdin.readline().strip()
	a = 0
	b = 0
	count = 0
	for i in s:
		if i == '(':
			a += 1
		elif i == ')':
			if a > 0:
				count += 1
				a -= 1
		elif i == '[':
			b += 1
		elif i == ']':
			if b > 0:
				count += 1
				b -= 1
	print(count)


n = int(input())
for k in range(n):
	x = input()
	par = 0
	cor = 0
	sal = 0
	for i in x:
		if i == '(':
			par += 1
		if i == '[':
			cor += 1
		if i == ')':
			if par > 0:
				sal += 1
				par -= 1
		if i == ']':
			if cor > 0:
				sal += 1
				cor -= 1
	print(sal)


for _ in range(int(input())):
	s = input()
	a = 0
	b = 0
	ans = 0
	for c in s:
		if c == '(':
			a += 1
		elif c == ')':
			if a > 0:
				a -= 1
				ans += 1
		elif c == '[':
			b += 1
		elif c == ']':
			if b > 0:
				b -= 1
				ans += 1
	print(ans)


def f(A, B):
	(i, j) = (0, 0)
	c = 0
	while i < len(A) and j < len(B):
		if A[i] < B[j]:
			c += 1
			i += 1
			j += 1
		else:
			j += 1
	return c
t = int(input())
for test in range(t):
	s = input()
	(ta, tc, qa, qc) = ([], [], [], [])
	for i in range(len(s)):
		if s[i] == '(':
			ta.append(i)
		elif s[i] == ')':
			tc.append(i)
		elif s[i] == '[':
			qa.append(i)
		else:
			qc.append(i)
	print(f(ta, tc) + f(qa, qc))


from sys import stdin, stdout
import math, sys, heapq
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import random
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		l = input()
		n = len(l)
		(nosq, noo) = (0, 0)
		ans = 0
		for i in range(n):
			if l[i] == '[':
				nosq += 1
			elif l[i] == '(':
				noo += 1
			elif l[i] == ')':
				if noo > 0:
					noo -= 1
					ans += 1
			elif l[i] == ']':
				if nosq > 0:
					nosq -= 1
					ans += 1
		print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


def two_brackets(s):
	normal_brackets = 0
	square_brackets = 0
	result = 0
	for letter in s:
		if letter == '(':
			normal_brackets += 1
		elif letter == '[':
			square_brackets += 1
		elif letter == ')' and normal_brackets > 0:
			normal_brackets -= 1
			result += 1
		elif letter == ']' and square_brackets > 0:
			square_brackets -= 1
			result += 1
	return result
for _ in range(int(input())):
	s = input()
	print(two_brackets(s))


for i in range(int(input())):
	s = input()
	cntsq = 0
	cntreg = 0
	cnt = 0
	for i in range(len(s)):
		if s[i] == '[':
			cntsq += 1
		elif s[i] == '(':
			cntreg += 1
		elif s[i] == ')':
			if cntreg != 0:
				cnt += 1
				cntreg -= 1
		elif cntsq != 0:
			cnt += 1
			cntsq -= 1
	print(cnt)


def solve():
	string = list(input().strip())
	d = {'(': 0, '[': 0}
	ans = 0
	for s in string:
		if s in d:
			d[s] += 1
		elif s == ')':
			if d['('] > 0:
				ans += 1
				d['('] -= 1
		elif s == ']':
			if d['['] > 0:
				d['['] -= 1
				ans += 1
	return ans
for _ in range(int(input().strip())):
	print(solve())


import sys
input = sys.stdin.readline
inputLines = sys.stdin.readlines

def readIntList():
	return list(map(int, input().split()))

def readStrList():
	return list(map(lambda x: x.strip(), inputLines()))

def indexOf(l: list, elem: int):
	return l.index(elem) if elem in l else -1

def lastIndexOf(l: list, elem: int):
	indexes = [idx for (idx, val) in enumerate(l) if val == elem]
	return max(indexes) if len(indexes) > 0 else -1

def solution():
	for _ in range(int(input())):
		s = input()
		c1 = 0
		c2 = 0
		counter = 0
		for i in range(len(s)):
			if s[i] == '(':
				c1 += 1
			if s[i] == ')' and c1 > 0:
				counter += 1
				c1 -= 1
			if s[i] == '[':
				c2 += 1
			if s[i] == ']' and c2 > 0:
				counter += 1
				c2 -= 1
		print(counter)
solution()


for i in ' ' * int(input()):
	s = input()
	stack1 = 0
	stack2 = 0
	ct1 = 0
	ct2 = 0
	for j in s:
		if j == '(':
			stack1 += 1
		if j == '[':
			stack2 += 1
		if j == ')':
			if stack1:
				stack1 -= 1
				ct1 += 1
		if j == ']':
			if stack2:
				stack2 -= 1
				ct2 += 1
	print(ct1 + ct2)


for _ in range(int(input())):
	x = input()
	l = 0
	m = 0
	n = 0
	for i in x:
		if i == '[':
			l += 1
		elif i == '(':
			m += 1
		elif i == ']' and l > 0:
			n += 1
			l -= 1
		elif i == ')' and m > 0:
			n += 1
			m -= 1
	print(n)


t = int(input())
for _ in range(t):
	s = input()
	(ans, x, y) = (0, 0, 0)
	for i in s:
		if i == ')' and x > 0:
			ans += 1
			x -= 1
		elif i == '(':
			x += 1
		elif i == ']' and y > 0:
			ans += 1
			y -= 1
		elif i == '[':
			y += 1
	print(ans)


def checker(s, a, b):
	cnt = 0
	switch = 0
	for elem in s:
		if elem == a:
			switch += 1
		elif elem == b and switch > 0:
			switch -= 1
			cnt += 1
	return cnt
for _ in range(int(input())):
	s = input()
	print(checker(s, '(', ')') + checker(s, '[', ']'))


from sys import stdin, stdout
from collections import Counter
from math import ceil, floor
from bisect import bisect_left
from bisect import bisect_right

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
for i in range(ip()):
	s = input()
	s = [i for i in s]
	(open_, close, open2, close2) = (0, 0, 0, 0)
	ans = 0
	for i in s:
		if i == '[':
			open2 += 1
		elif i == ']' and open2 > 0:
			open2 -= 1
			ans += 1
		if i == '(':
			open_ += 1
		elif i == ')' and open_ > 0:
			open_ -= 1
			ans += 1
	print(ans)


test_cases = int(input())
for _ in range(test_cases):
	s = input()
	marcas = [0, 0]
	res = 0
	for char in s:
		if char == '(':
			marcas[0] += 1
		elif char == ')':
			if marcas[0] != 0:
				res += 1
				marcas[0] -= 1
		elif char == ']':
			if marcas[1] != 0:
				res += 1
				marcas[1] -= 1
		else:
			marcas[1] += 1
	print(res)


def solve(s):
	open = close = 0
	open_t = close_t = 0
	for c in s:
		if c == '(' or c == ')':
			if c == '(':
				open += 1
			elif open > close:
				close += 1
		elif c == '[':
			open_t += 1
		elif open_t > close_t:
			close_t += 1
	return min(open, close) + min(open_t, close_t)
t = int(input())
while t:
	s = input()
	print(solve(s))
	t -= 1


def find_max_ways(s):
	count = c1 = c2 = 0
	for i in s:
		if i == '(':
			c1 += 1
		elif i == '[':
			c2 += 1
		if i == ')':
			if c1 > 0:
				count += 1
				c1 -= 1
		elif i == ']':
			if c2 > 0:
				count += 1
				c2 -= 1
	return count
t = int(input())
for i in range(t):
	s = input()
	print(find_max_ways(s))


for i in range(int(input())):
	st = input()
	ll = []
	ll2 = []
	s = 0
	for j in st:
		if j == '(':
			ll.append(')')
		elif j == '[':
			ll2.append(']')
		elif j == ')':
			if len(ll) > 0 and j == ll.pop():
				s += 1
		elif j == ']':
			if len(ll2) > 0 and j == ll2.pop():
				s += 1
	print(s)


def main():
	t = int(input())
	brackets = {'(': 1, ')': -1, '[': 2, ']': -2}
	for _ in range(t):
		count = 0
		s = input()
		stack1 = []
		stack2 = []
		for i in s:
			if brackets[i] == 1:
				stack1.append(i)
			elif brackets[i] == 2:
				stack2.append(i)
			elif brackets[i] == -1:
				if len(stack1) == 0:
					continue
				if brackets[i] + brackets[stack1[-1]] == 0:
					stack1.pop()
					count += 1
			else:
				if len(stack2) == 0:
					continue
				if brackets[i] + brackets[stack2[-1]] == 0:
					stack2.pop()
					count += 1
		print(count)
main()


def run():
	t = int(input())
	for _ in range(t):
		s = input()
		counter = 0
		c_ro = 0
		c_sq = 0
		for c in s:
			if c == '[':
				c_sq += 1
			elif c == '(':
				c_ro += 1
			elif c == ']':
				if c_sq > 0:
					c_sq -= 1
					counter += 1
			elif c == ')':
				if c_ro > 0:
					c_ro -= 1
					counter += 1
		print(counter)
run()