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。