Yuki 發現回文括號序列唔可能係平衡括號序列，所以佢設計咗另一種方法去定義回文平衡括號序列。
Yuki 用以下規則定義回文括號序列：
空字串係回文括號序列。
(同)都係回文括號序列。如果括號序列 $s$ 係回文括號序列，咁 $(s($ 同 $)s)$ 都係回文括號序列。
Yuki 用以下規則定義平衡括號序列：
空字串係平衡括號序列。
如果括號序列 $s$ 係平衡括號序列，咁 $(s)$ 係平衡括號序列。
如果括號序列 $s$ 同 $t$ 都係平衡括號序列，咁 $st$（將呢兩個括號序列串接起嚟）都係平衡括號序列。
對於括號序列 $s=s_1\ldots s_n$，Yuki 定義 $s$ 係回文平衡括號序列，當且僅當：
$s_2\ldots s_{n-1}$ 係回文括號序列。
$s_1\ldots s_n$ 係平衡括號序列。
特別係，空字串同 () 都係回文平衡括號序列。
例如，(())() 同 ()()(()()) 係回文平衡括號序列，而 ((())) 同 ()()(()) 就唔係。
而家 Yuki 有一個長度係 $n$ 嘅括號序列 $s$，佢想搵出 $s$ 入面最長而且係回文平衡括號序列嘅子序列*。但係 Yuki 唔知點樣做，所以你需要幫佢搵出呢種最長子序列嘅長度。
*：序列 $a$ 係序列 $b$ 嘅子序列，當且僅當可以由 $b$ 刪走零個或者多個元素得到 $a$；特別係，空序列係任何序列嘅子序列。
輸入格式
呢題包含多組測試資料。
第一行有一個正整數 $t$（$1\le t\le5000$），表示測試資料嘅組數。
對於每組測試資料：
第一行有一個正整數 $n$（$1\le n\le5000$）。
第二行有一個長度係 $n$ 嘅括號序列 $s$（$s_i\in\{\texttt{(},\texttt{)}\}$）。
保證所有測試資料嘅 $n$ 總和唔超過 $10^4$。
輸出格式
對於每組測試資料，輸出一行，當中有一個整數，表示符合條件嘅最長子序列嘅長度。
樣例
輸入格式 1
3 5 (()(( 7 )))(((( 8 ())(()()
輸出格式 1
2 0 6
說明
對於第一組測試資料：
- 符合條件嘅最長子序列係 $s_1s_3=\texttt{()}$ 同 $s_2s_3=\texttt{()}$，所以答案係 2。
對於第二組測試資料：
- 符合條件嘅最長子序列係空字串，所以答案係 0。
對於第三組測試資料：
- 符合條件嘅最長子序列係 $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$，所以答案係 6。