This is the easy version of the problem. The difference between the versions is that in this version, you only need to evaluate for whole string $s$, $s$ is regular, and the constraints on $n$ are higher.

We say that a bracket sequence $a$ is better than a bracket sequence $b$ if one of the following holds:

• $b$ is a prefix of $a$, but $a \ne b$; or
• let $i$ be the first position (if it exists) where $a_i \neq b_i$, then $\color{red}{a_i = \texttt{(}}$ and $\color{red}{b_i = \texttt{)}}$.

You are given a regular bracket sequence$^{\text{∗}}$ $s$ of even length $n$.

Among all non-empty subsequences $^{\text{†}}$ $t$ of $s$ that are regular bracket sequences, find the maximum possible length of $t$ such that $t$ is better than $s$. If no such $t$ exists, report it.

$^{\text{∗}}$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $\texttt{1}$ and $\texttt{+}$ between the original characters of the sequence. For example: bracket sequences $\texttt{()()}$ and $\texttt{(())}$ are regular (the resulting expressions are $\texttt{(1)+(1)}$ and $\texttt{((1+1)+1)}$); bracket sequences $\texttt{)(}$, $\texttt{(}$, and $\texttt{)}$ are not. $^{\text{†}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$, $n$ is even) — the length of the string $s$.

The second line of each test case contains a sequence $s$ of length $n$ consisting only of characters $\texttt{(}$ and $\texttt{)}$.

It is guaranteed that the given sequence $s$ is a regular bracket sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the maximum possible length of a non-empty subsequence $t$ of $s$ that is a regular bracket sequence and is better than $s$. If no such $t$ exists, print $-1$.

Note

In the first example, the only non-empty regular bracket subsequence of $s$ is $t = s = \texttt{()}$. Since $t$ is not better than $s$, we output $-1$.

In the second example, we can choose $t = \texttt{((()))}$. The first index where $t$ and $s$ differ is $i = 3$. Since $t_3 = \texttt{(}$ and $s_3 = \texttt{)}$, $t$ is better than $s$. We cannot choose a longer subsequence because the only longer regular bracket subsequence is $s$ itself, which is not better than $s$. Thus, we output $6$.