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.

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.

Bring Balance

Examples