H. Balance The sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Yessine received a balanced sequence of brackets $$$s$$$ of length $$$n$$$ , unfortunately, someone took a contiguous subsequence $$$s[i..j]$$$ and reversed it.

Yessine wants to rebalance the sequence again , please help him to find any pair $$$(i,j)$$$ such that if you reverse the subsequence $$$s[i..j]$$$, the sequence becomes balanced.

For example, if $$$n = 8$$$ and $$$s$$$ = $$$())()(()$$$, to make s balanced, you can choose $$$i = 2$$$ and $$$j = 7$$$, $$$s$$$ will become $$$((()()))$$$.

Input

The first line contains the number of test cases t $$$(1 \le t \le 10^3)$$$

The first line of each test case contains one even integer $$$n$$$ $$$(2 \le n \le 5.10^3)$$$ — the length of the sequence $$$s$$$.

The second line of each test case contains a string consisting of $$$n$$$ brackets.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, print one line containing two integer : $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le n)$$$

If there are multiple solutions, print any.

Example
Input
2
8
())()(()
8
))))((((
Output
2 7
1 8