七天假日 题目描述 Saki 在 Koboshi 的安利下开始玩起了一款简单的游戏。 游戏中，每个关卡会给你一个合法的括号串。合法的括号串定义如下： 空串和 () 为合法的括号串； 设 A 为合法

七天假日

题目描述

Saki 在 Koboshi 的安利下开始玩起了一款简单的游戏。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

游戏中，每个关卡会给你一个合法的括号串。合法的括号串定义如下：qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

• 空串和 () 为合法的括号串；
• 设 A 为合法的括号串，那么 (A) 为合法的括号串；
• 设 A 和 B 为合法的括号串，那么 AB 为合法的括号串。

游戏中，每次操作可以交换两个相邻的括号，而游戏的目标是通过若干次操作使括号串变得非法。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

而 Saki 并不知道自己的操作数是否已经优化到最少，所以她想问游戏领域大神 Koboshi 她的操作数是否是最少的。而 Koboshi 因为手和脚都在玩游戏，所以她把这件事情丢给了你，让你求得通关所需最少的操作次数。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当然游戏有 T 个关卡，Saki 需要知道每一关通关所需的最少操作次数。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

第一行一个正整数 T，代表关卡数量。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来 T 行，每行一个合法的括号串，表示每一关给出的括号串。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

共 T 行，第 i 行表示通过第 i 关所需要的最少的操作次数。qC5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

数据范围

• 对于 30% 的数据，1≤T≤100，2≤n≤8；
• 对于另外 30%的数据，1≤T≤50，2≤n,∑n≤100；
• 对于 100%100% 的数据，1≤T≤10^5，2≤n,∑n≤10^6。保证 S 是合法的括号序列。

样例数据