题目描述

薯条哥有一个括号序列，该括号序列由两种括号组成{}和[]。薯条哥的括号序列中所有的左括号序列个数是等于右括号序列个数的，

但是可能有左括号无法和右括号匹配或者右括号无法和左括号匹配的情况。

薯条哥每一次可以修改序列中某一个括号的种类即{→[，[→{或}→]，]→}。

薯条哥想知道他最少修改多少次可以使得每个左括号都有对应右括号与之匹配呢，即使得括号序列合法。

括号列合法的定义如下:

1.{},[]是合法的括号序列。

2.若$A$为合法的括号序列，则{$A$},$[A]$是合法的括号序列。

3.若$A,B$为合法的括号序列，则$AB$, $BA$为合法的括号序列。

输入描述

第一行输入为$t(1\le t\le 100)$，表示有$t$组数据。

接下来有$t$行，每行为一个字符串表示括号序列$str(1\le \mid str\mid\le 10^5,\sum \mid str\mid\le 10^5)$。

数据保证忽略括号类型时，初始序列左括号和右括号是合法的。

输出描述

输出为$t$行，每行为一组答案，即最少修改次数。

样例

输入

2
{[][}}
[][]{{]]

输出

1
2

样例解释

第一组中可以将最后一个括号}修改为]，使得每个括号都可以匹配，只需要修改一次。

第二组中可以将最后两个}修改为]。