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$에서 0개 이상의 원소를 삭제하여 얻어질 수 있을 때 그리고 그때에만 $a$를 $b$의 부분 수열이라고 합니다. 특별히 빈 수열은 모든 수열의 부분 수열입니다.
입력 형식
이 문제는 여러 개의 테스트 케이스를 포함합니다.
첫 번째 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $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입니다.