اكتشفت 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.