2857：括号匹配

给定一个由$$()[]$$括号组成的字符串$$S$$

从形式上讲，只有满足下面几点之一，括号字符串才是合法的：

1、空串

2、如果一个串$$S$$是合法的，那么$$(S)$$、$$[S]$$也是合法的

3、如果$$a$$和$$b$$是合法的，那么$$ab$$也是合法的

下面几个串是合法的：

()
[]
(())
()[]
()[()]

下面几个串是不合法的：

(
]
)(
([)]
([(]

给出一个括号串，请问至少需要加几个括号才能使其变得合法。

第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \le T \le 100$$）

每组案例包含一个长度不超过$$100$$的括号串。

针对每组样例，在一行中输出至少需要加几个括号才能使括号串变得合法。

2

[])

()())(

1

2

题单#22（动态规划之区间DP）