33841번 - 괄호 뒤집기 스페셜 저지

문제

( $N$개와 ) $N$개로 이뤄진 괄호문자열 $S$가 주어진다. 다음 시행을 최소로 하여 올바른 괄호문자열을 만들어라.

• 1ドル \leq l \leq r \leq 2N$인 두 정수 $l,ドル $r$을 고른다. 이후 $S_l, S_{l+1}, \cdots , S_r$로 이뤄진 부분 문자열을 뒤집는다. 즉, $S_l, S_{l+1}, \cdots , S_r$을 각각 $S_r, S_{r-1}, \cdots , S_l$로 바꾼다.

올바른 괄호 문자열의 정의는 다음과 같다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. A가 올바른 괄호 문자열이라면, (A)도 올바른 괄호 문자열이다.
3. A와 B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열이다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 10\ 000)$

각 테스트 케이스의 첫 번째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 300\ 000)$

두 번째 줄에 ( $N$개와 ) $N$개로 이뤄진 문자열 $S$가 주어진다.

모든 테스트 케이스에서 $N$의 합은 300ドル\ 000$을 넘지 않는다.

출력

각 테스트 케이스마다 첫 번째 줄에 필요한 시행의 최소 횟수 $K$를 출력한다. 문제의 제약 조건 하에서 항상 $K \leq N$임을 보일 수 있다.

다음 $K$개의 줄에 각 시행을 나타내는 두 정수 $l,ドル $r$을 공백으로 구분해 출력한다.

제한

노트

( 를 뒤집어도 )가 되지 않는다는 점을 유의하자.