C. Bring Balance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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.

Example
Input
3
2
(())
5
())((()))(
6
())((()))(()
Output
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.