## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Bring Balance Codeforces Solution | Codeforces Problem Solution 2022

E. 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$ $\left(0\le k\le n\right)$  — 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}_{l}{s}_{l+1}\dots {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.