Maximum Bracket Distance - Repovive Opening Round | Repovive

0D. Maximum Bracket Distance

2000 pts2s256 MB

A valid bracket sequence is a string consisting of characters ( and ) such that:

Every prefix contains at least as many ( as )
The total number of ( equals the total number of )

For example, (()), ()(), and (()()) are valid, while )(, ((), and ()) are not.

The distance between two strings of equal length is the number of positions where they differ.

Given a valid bracket sequence $S$ of length $2n$ , find the maximum possible distance from $S$ to any other valid bracket sequence of the same length.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \\ S \end{array} \right\} \times t

Output

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_t \end{array}

Samples

Input

4
2
(())
3
((()))
3
()(())
1
()

Explanation

Sample tests: basic nested, larger nested, mixed (false intuition trap), edge n=1.

Output

A valid bracket sequence is a string consisting of characters ( and ) such that:

Every prefix contains at least as many ( as )
The total number of ( equals the total number of )

For example, (()), ()(), and (()()) are valid, while )(, ((), and ()) are not.

The distance between two strings of equal length is the number of positions where they differ.

Given a valid bracket sequence $S$ of length $2n$ , find the maximum possible distance from $S$ to any other valid bracket sequence of the same length.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \\ S \end{array} \right\} \times t

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_t \end{array}

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

0D. Maximum Bracket Distance

Input

Output

Samples

0D. Maximum Bracket Distance

Constraints

Input

Output

Samples

Constraints