Bring Balance
Description
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.
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$.
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.
Input
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$.
Output
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.
Samples
3
2
(())
5
())((()))(
6
())((()))(()
0
2
3 4
9 10
1
2 11
Note
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.