dXqwq 和 Haitang 在玩一个括号串上的游戏。
有一个初始全为黑色的括号串 S，两个人各有一把刷子，dXqwq 的刷子是红色的，Haitang 的刷子是蓝色的。
她们会依次执行以下操作，直到所有括号都被染色，且 dXqwq 先执行操作：

• 选择一个没有被染色的括号，用自己的刷子将它染色。

在操作后，dXqwq 会取出红色括号的一个可以匹配的子序列，并将其长度的一半定义为游戏分数。
dXqwq 希望最大化游戏分数，而 Haitang 则希望最小化这个值，你需要输出两人都在最优策略下操作后的游戏分数。

本题有多组测试数据。
第一行输入一个整数 T，代表数据组数。
接下来 T 行，每行输入一个括号串 S。

对于每组数据输出一行一个整数，代表最优策略下的游戏分数。

第八题