C. Привнеси баланс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алины есть скобочная последовательность $$$s$$$ длины $$$2n$$$, состоящая из $$$n$$$ открывающих скобок '(' и $$$n$$$ закрывающих скобок ')'. Поскольку ей нравится баланс, она хочет превратить эту последовательность скобок в сбалансированную скобочную последовательность.

За одну операцию она может развернуть любую подстроку $$$s$$$.

Какое наименьшее количество операций ей потребуется, чтобы превратить $$$s$$$ в сбалансированную скобочную последовательность? Можно показать, что это всегда можно сделать за не более чем $$$n$$$ операций.

Напомним, что скобочная последовательность называется сбалансированной, если ее можно превратить в правильное математическое выражение, добавив символы + и 1. Например, последовательности (())(), () и (()(())) являются сбалансированными, а )(, (() и (())(  — нет.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$2n$$$, состоящую из $$$n$$$ открывающих и $$$n$$$ закрывающих скобок.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в первой строке выведите одно целое число $$$k$$$ $$$(0 \le k \le n)$$$  — наименьшее количество необходимых операций.

В $$$i$$$-й из следующих $$$k$$$ строк должны содержаться два целых числа $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 2n$$$), указывающие на то, что в $$$i$$$-й операции Алина развернет подстроку $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$. Здесь нумерация начинается с $$$1$$$.

Если существует несколько последовательностей операций с наименьшей длиной, которые преобразуют последовательность в сбалансированную, вы можете вывести любую из них.

Пример
Входные данные
3
2
(())
5
())((()))(
6
())((()))(()
Выходные данные
0
2
3 4
9 10
1
2 11
Примечание

В первом наборе входных данных строка уже сбалансирована.

Во втором наборе входных данных строка будет преобразована следующим образом: ())(()))( $$$\to$$$ ()()()())( $$$\to$$$ ()()()()(), где последняя строка сбалансирована.

В третьем наборе входных данных строка будет преобразована в ((()))((())), которая является сбалансированой.