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 רצף סוגריים $s$ באורך $n$, והיא רוצה למצוא את תת-הרצף* הארוך ביותר של $s$ שהוא רצף סוגריים פלינדרומי מאוזן. אולם Yuki אינה יודעת כיצד לעשות זאת, ולכן עליך לעזור לה למצוא את אורכו של תת-הרצף הארוך ביותר מסוג זה.

*: רצף $a$ הוא תת-רצף של רצף $b$ אם ורק אם אפשר לקבל את $a$ על ידי מחיקת אפס איברים או יותר מ-$b$; בפרט, הרצף הריק הוא תת-רצף של כל רצף.

קלט

בעיה זו מכילה מספר מקרי בדיקה.

השורה הראשונה מכילה מספר שלם חיובי $t$ ($1\le t\le5000$), המייצג את מספר מקרי הבדיקה.

לכל מקרה בדיקה:

• השורה הראשונה מכילה מספר שלם חיובי $n$ ($1\le n\le5000$).

• השורה השנייה מכילה רצף סוגריים $s$ באורך $n$ ($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.