Alina 有一个长度为 $$$2n$$$ 的括号序列 $$$s$$$,由 $$$n$$$ 左括号 '(' 和 $$$n$$$ 右括号 ')' 组成。由于她喜欢平衡,所以她想把这个括号序列变成平衡的括号序列。
在一次操作中,她可以反转 $$$s$$$ 的任何子字符串。
将 $$$s$$$ 转变为平衡括号序列所需的最少操作次数是多少?可以证明,最多 $$$n$$$ 次操作始终是可能的。
提醒一下,如果可以通过添加字符 + 和 1 将括号序列转换为有效的数学表达式,则该序列称为平衡的。例如,序列 (())()、() 和 (()(())) 是平衡的,而 )(、(() 和 (()))( 不是平衡的。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
每个测试用例的第二行包含一个长度为$$$2n$$$的字符串$$$s$$$,由$$$n$$$左括号和$$$n$$$右括号组成。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在第一行输出一个整数 $$$k$$$ $$$(0 \le k \le n)$$$ — 所需的最小操作数。
接下来的 $$$k$$$ 行的第 $$$i$$$ 行应包含两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 2n$$$),表示在第 $$$i$$$ 操作中,Alina 将反转子字符串 $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$。这里从$$$1$$$开始计数。
如果有多个最小长度的操作序列将序列转换为平衡序列,则可以输出其中任何一个。
示例
输入 #1
3 2 (()) 5 ())((()))( 6 ())((()))(()
输出 #1
0 2 3 4 9 10 1 2 11
注意
在第一个测试用例中,字符串已经平衡。
在第二个测试用例中,字符串将按如下方式转换: ())((()))( $$$\to$$$ ()()(()))( $$$\to$$$ ()()(())(),其中最后一个字符串是平衡的。
在第三个测试用例中,字符串将被转换为 ((()))((())),这是平衡的。