Yuki menemukan bahwa barisan tanda kurung palindromik tidak dapat menjadi barisan tanda kurung seimbang, sehingga ia merancang cara lain untuk mendefinisikan barisan tanda kurung palindromik seimbang.

Yuki mendefinisikan barisan tanda kurung palindromik berdasarkan aturan berikut:

• String kosong adalah barisan tanda kurung palindromik.

• ( dan ) adalah barisan tanda kurung palindromik.

• Jika barisan tanda kurung $s$ adalah barisan tanda kurung palindromik, maka $(s($ dan $)s)$ juga merupakan barisan tanda kurung palindromik.

Yuki mendefinisikan barisan tanda kurung seimbang berdasarkan aturan berikut:

• String kosong adalah barisan tanda kurung seimbang.

• Jika barisan tanda kurung $s$ adalah barisan tanda kurung seimbang, maka $(s)$ juga merupakan barisan tanda kurung seimbang.

• Jika barisan tanda kurung $s$ dan $t$ keduanya merupakan barisan tanda kurung seimbang, maka $st$ (penggabungan kedua barisan tanda kurung) merupakan barisan tanda kurung seimbang.

Untuk barisan tanda kurung $s=s_1\ldots s_n$, Yuki mendefinisikan $s$ sebagai barisan tanda kurung palindromik seimbang jika dan hanya jika:

• $s_2\ldots s_{n-1}$ adalah barisan tanda kurung palindromik.

• $s_1\ldots s_n$ adalah barisan tanda kurung seimbang.

Secara khusus, string kosong dan () juga merupakan barisan tanda kurung palindromik seimbang.

Sebagai contoh, (())() dan ()()(()()) adalah barisan tanda kurung palindromik seimbang, sedangkan ((())) dan ()()(()) bukan.

Sekarang Yuki memiliki barisan tanda kurung $s$ dengan panjang $n$, dan ia ingin mencari subsekuens* terpanjang dari $s$ yang merupakan barisan tanda kurung palindromik seimbang. Namun, Yuki tidak tahu caranya, sehingga Anda perlu membantunya mencari panjang subsekuens terpanjang tersebut.

*: Barisan $a$ adalah subsekuens dari barisan $b$ jika dan hanya jika $a$ dapat diperoleh dengan menghapus nol atau lebih elemen dari $b$; secara khusus, barisan kosong adalah subsekuens dari barisan apa pun.

Masukan

Soal ini berisi beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat positif $t$ ($1\le t\le5000$) yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi sebuah bilangan bulat positif $n$ ($1\le n\le5000$).

• Baris kedua berisi barisan tanda kurung $s$ dengan panjang $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Dijamin bahwa jumlah $n$ untuk seluruh kasus uji tidak melebihi $10^4$.

Keluaran

Untuk setiap kasus uji, cetak satu baris berisi sebuah bilangan bulat yang menyatakan panjang subsekuens terpanjang yang memenuhi syarat.

Contoh

Masukan 1

3
5
(()((
7
)))((((
8
())(()()

Keluaran 1

2
0
6

Catatan

Untuk kasus uji pertama:

• Subsekuens terpanjang yang memenuhi syarat adalah $s_1s_3=\texttt{()}$ dan $s_2s_3=\texttt{()}$, sehingga jawabannya 2.

Untuk kasus uji kedua:

• Subsekuens terpanjang yang memenuhi syarat adalah string kosong, sehingga jawabannya 0.

Untuk kasus uji ketiga:

• Subsekuens terpanjang yang memenuhi syarat adalah $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, sehingga jawabannya 6.