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.

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.

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.