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