CF1685C.Bring Balance

Alina has a bracket sequence $s$ of length $2n$, consisting of $n$ opening brackets '(' and $n$ closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence.

In one operation, she can reverse any substring of $s$.

What's the smallest number of operations that she needs to turn $s$ into a balanced bracket sequence? It can be shown that it's always possible in at most $n$ operations.

As a reminder, a sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.

阿丽娜有一个长度为 $2n$ 的括号序列 $s$，其中包含 $n$ 个左括号 '(' 和 $n$ 个右括号 ')'。由于她喜欢“平衡”，她希望将该括号序列变为一个平衡括号序列。

在一次操作中，她可以翻转 $s$ 的任意一个子串。

请问：将 $s$ 变为平衡括号序列所需的最少操作次数是多少？可以证明，至多只需 $n$ 次操作即可完成。

作为提示：若一个括号序列可通过添加字符 + 和 1 转化为一个合法的数学表达式，则称其为平衡括号序列。例如，序列 (())()、() 和 (()(())) 是平衡的，而 )(、(() 和 (()))( 则不是。

The first line of the input contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains a string $s$ of length $2n$, consisting of $n$ opening and $n$ closing brackets.

The sum of $n$ over all test cases doesn't exceed $2\cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含一个长度为 $2n$ 的字符串 $s$，该字符串由 $n$ 个左括号和 $n$ 个右括号组成。

所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, in the first line output a single integer $k$ $(0 \le k \le n)$ — the smallest number of operations required.

The $i$-th of the next $k$ lines should contain two integers $l_i, r_i$ ($1 \le l_i \le r_i \le 2n$), indicating that in the $i$-th operation, Alina will reverse the substring $s_ls_{l+1} \ldots s_{r-1}s_r$. Here the numeration starts from $1$.

If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them.

对于每个测试用例，在第一行输出一个整数 $k$（$0 \le k \le n$）—— 即将序列变为平衡序列所需的最少操作次数。

接下来的 $k$ 行中，第 $i$ 行应包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le 2n$），表示在第 $i$ 次操作中，Alina 将反转子串 $s_ls_{l+1} \ldots s_{r-1}s_r$。此处下标从 $1$ 开始计数。

若存在多个长度最短的操作序列可将序列变为平衡序列，你可以输出其中任意一个。

In the first test case, the string is already balanced.

In the second test case, the string will be transformed as follows: ())((()))( $\to$ ()()(()))( $\to$ ()()(())(), where the last string is balanced.

In the third test case, the string will be transformed to ((()))((())), which is balanced.

在第一个测试用例中，该字符串已经是平衡的。

在第二个测试用例中，该字符串将按如下方式变换：())((()))( $\to$ ()()(()))( $\to$ ()()(())()，其中最终的字符串是平衡的。

在第三个测试用例中，该字符串将变换为 ((()))((()))，它是平衡的。