CF1657C.Bracket Sequence Deletion

You are given a bracket sequence consisting of $n$ characters '(' and/or )'. You perform several operations with it.

During one operation, you choose the shortest prefix of this string (some amount of first characters of the string) that is good and remove it from the string.

The prefix is considered good if one of the following two conditions is satisfied:

• this prefix is a regular bracket sequence;
• this prefix is a palindrome of length at least two.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not.

The bracket sequence is called palindrome if it reads the same back and forth. For example, the bracket sequences )), (( and )(() are palindromes, while bracket sequences (), )( and ))( are not palindromes.

You stop performing the operations when it's not possible to find a good prefix. Your task is to find the number of operations you will perform on the given string and the number of remaining characters in the string.

You have to answer $t$ independent test cases.

给你一个由 $n$ 个字符 '(' 和/或 ')' 组成的括号序列。你需要对该序列执行若干次操作。

每次操作中，你需选择该字符串的最短前缀（即字符串开头的若干连续字符），该前缀必须是“好”的，并将它从字符串中移除。

当满足以下两个条件之一时，该前缀被称为“好”的：

• 该前缀是一个合法括号序列；
• 该前缀是一个长度至少为 2 的回文串。

若能通过在该括号序列中插入字符 '+' 和 '1' 得到一个合法的算术表达式，则称该括号序列为合法括号序列。例如，序列 (())()、() 和 (()(())) 是合法的，而 )(、(() 和 (()))( 则不是。

若一个括号序列正读与反读完全相同，则称其为回文串。例如，括号序列 ))、( ( 和 )(() 是回文串，而 ()、)( 和 ))( 则不是回文串。

当无法再找到“好”的前缀时，操作停止。你的任务是：对给定字符串，求出总共执行的操作次数以及最终剩余的字符数。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The next $2t$ lines describe test cases.

The first line of the test case contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of the bracket sequence.

The second line of the test case contains $n$ characters '(' and/or ')' — the bracket sequence itself.

It is guaranteed that the sum of $n$ over all test cases do not exceed $5 \cdot 10^5$ ($\sum n \le 5 \cdot 10^5$).

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来的 $2t$ 行描述各个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示括号序列的长度。

每个测试用例的第二行包含 $n$ 个字符，每个字符为 '(' 或 ')'，即括号序列本身。

保证所有测试用例的 $n$ 值之和不超过 $5 \cdot 10^5$（即 $\sum n \le 5 \cdot 10^5$）。

For each test case, print two integers $c$ and $r$ — the number of operations you will perform on the given bracket sequence and the number of characters that remain in the string after performing all operations.

对于每个测试用例，输出两个整数 $c$ 和 $r$ —— 分别表示对给定括号序列执行的操作次数，以及执行所有操作后字符串中剩余的字符数量。