**Happy Trees**

You’re given a balanced bracket expression. In the forest representation of it, find the number of trees which are happy. A happy tree is a tree in which every vertex other than the leaves has the same number of children. A tree with just one vertex would also be considered happy.

**Input Format**

First line of input consists of an integer t denoting the number of test cases. First line of each test case consists of an integer n denoting the length of the expression. Second line consists of the bracket expression.

**Output Format**

For each test case, find the number of trees which are happy.

**Constraints**

1 <= t <= 1000

n = 2 * m where 1 <= m <= 1000

**Sample Input**

4

12

[[[][]][[]]]

20

[[[][][]][][[][][]]]

14

[[]][[][[]]][]

28

[[[][]][[][]]][[][]][[[[]]]]

**Sample Output**

0

1

2

3

**Explanation**

The expression [[[][]][[]]] has the following representation

[]

├── []

│ ├── []

│ └── []

└── []

└── []

There is only one tree. Root and second child of root has two children each. First child of root has only one child. It’s not happy.

The expression [[[][][]][][[][][]]] has the following representation

[]

├── []

│ ├── []

│ ├── []

│ └── []

├── []

└── []

├── []

├── []

└── []

There is only one tree. All non-leaf vertices have exactly 3 children. Tree is happy.

The expression [[]][[][[]]][] has the following representation

[]

└── []

[]

├── []

└── []

└── []

[]

There are three trees. Only two of them are happy.

The expression [[[][]][[][]]][[][]][[[[]]]] has the following representation

[]

├── []

│ ├── []

│ └── []

└── []

├── []

└── []

[]

├── []

└── []

[]

└── []

└── []

└── []

The number of happy trees is 3.