890 . Yet Another Answer
Description
Eventually, after running Yet Another Stupendous Supercomputer for π million of years, hedgehogs happen to know Yet Another Answer. This time the Answer they got was quite surprising. Even for hedgehogs who didn't actually know what the Question was.
In fact, the Answer consists of n words. Each word is a nonempty sequence of left and right brackets.
Whilst most of the hedgehogs were rather frustrated with the Answer, Fluffy was happy, because Fluffy likes brackets so much. But most of all he likes regular bracket sequences.
A regular bracket sequence is a sequence of brackets which satisfies the following conditions:
Fluffy is sure that it's vitally important for the hedgehogs to know what is the longest regular bracket sequence one can make by concatenating the words of the Answer under the following rules:
Because the Supercomputer is so busy designing its yet more powerful successor, Fluffy hopes you can help him to solve the problem.
<!--
-->
Input Format
The first line contains an integer T<=100 indicating the number of test cases. For each test case, the first line contains the number of words in the Answer n (1 ≤ n ≤ 1000). Each of the next n lines contains one of these words. The total length of all words doesn't exceed 10000.
Output Format
For each test case, please output a line containing the length of the longest possible regular bracket sequence.
Sample Input 1
2 4 ( ((( ( )) 3 () (() )
Sample Output 1
4 6
Hints
Problem Source
Migrated from old NTUJ.
Ural 1745
Subtasks
| No. | Testdata Range | Score |
|---|