Jang Deok-su is down on his luck, having accumulated enormous debts with loan sharks. He needs to solve a problem so that he can repay his loan. Since you are his teammate, help him solve the problem for your own survival.  RECode 20.0 » Deok-su and his Debts

Deok-su and his Debts Problem Code: REC20B


Add problem to Todo list
Submit
Jang Deok-su is down on his luck, having accumulated enormous debts with loan sharks. He needs to solve a problem so that he can repay his loan. Since you are his teammate, help him solve the problem for your own survival.

In the problem is given a string containing, 'c' or '+'. A Complete String is a non-empty string that consists of consecutive occurrences of "c++", any number of times.

For example, "c++", "c++c++", "c++c++c++c++" are Complete String, whereas
"+c++", "c+c++", "c++c" are not.

You can form a Complete String (if possible) by removing some of the characters from the string (possibly 0).

Your task is to remove minimum number of the characters from the string (possibly 0), such that no Complete String can be formed from the resulting string.

When you remove a character from a string, the adjacent characters (if any) come together to fill the gap.

Input Format

First-line contains T − number of test cases.
First line of each test case contains N − length of each string.
Second line of each test case contains S − String containing 'c' and/or '+'.

Output Format

For each test case, a single integer in separate lines − minimum number of characters to be removed such that no Complete String can be formed from the resulting string.

Constraints

1≤T≤50
1≤N≤105
S⊂ {'c', '+'}

Sample Input 1 

5
6
c++c++
6
+ccc++
5
++c++
8
cc++++++
3
c++

Sample Output 1 

2
1
1
2
1

Explanation

Test 1: We can remove characters from indices 0 and 3 to form

Test 5: We can remove any one of the characters, then you can't form a Complete String.