Chiaki 有 $n$ 个由 '(' 和 ')' 组成的字符串 $s_1, s_2, \dots, s_n$。如果一个此类字符串满足以下条件，则称其为平衡的：
- 它是空字符串；
- 如果 $A$ 和 $B$ 是平衡的，则 $AB$ 是平衡的；
- 如果 $A$ 是平衡的，则 $(A)$ 是平衡的。
Chiaki 可以重新排列这些字符串并将其连接成一个新的字符串 $t$。令 $f(t)$ 为 $t$ 的最长平衡子序列（不一定连续）的长度。Chiaki 想知道对于所有可能的 $t$， $f(t)$ 的最大值是多少。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：
第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示字符串的数量。 接下来的 $n$ 行，每行包含一个由 '(' 和 ')' 组成的字符串 $s_i$ ($1 \le |s_i| \le 10^5$)。
保证所有 $|s_i|$ 的总和不超过 $5 \times 10^6$。
输出格式
对于每组测试数据，输出一个整数表示答案。
样例
输入 1
2 1 )()(()( 2 ) )(
输出 1
4 2