0.4 Fighting Monsters

Score: 10pts

Time Limit: 2.00 sec

You are an immortal Monster Slayer. Initially your health H is 0.

You need to fight N monsters represented by string S.

Using the string S you perform the following operations N times.

In the i-th operation, your health gets incremented by 1 if the monster is Idiot which is represented by Si = ‘I’ and health gets decremented by 1 if the monster is dangerous for which Si=’D’.

Find the maximum health during the operations (including before the first operation, and after the last operation).

You need to fight N monsters represented by string S.

Using the string S you perform the following operations N times.

In the i-th operation, your health gets incremented by 1 if the monster is Idiot which is represented by Si = ‘I’ and health gets decremented by 1 if the monster is dangerous for which Si=’D’.

Find the maximum health during the operations (including before the first operation, and after the last operation).

Constraints

1≤T≤100

∣S∣ = Length of String

No characters except I and D occur in S.

∣S∣ = Length of String

No characters except I and D occur in S.

Input Format

T

S

S

Output Format

Print the maximum health achieved during N operations.

Example 1

Input:

2

IIDID

IIDDIIIDD

Output:

2

3

Explanation:

Case -1 : After each operation, the value of x becomes 1, 2, 1, 2 and 1, respectively. Thus, the output should be 2, the maximum health.

Case -2 : After each operation , the value of x becomes {1 , 2 , 1 , 0 , 1 , 2 , 3 , 2 , 1}

2

IIDID

IIDDIIIDD

Output:

2

3

Explanation:

Case -1 : After each operation, the value of x becomes 1, 2, 1, 2 and 1, respectively. Thus, the output should be 2, the maximum health.

Case -2 : After each operation , the value of x becomes {1 , 2 , 1 , 0 , 1 , 2 , 3 , 2 , 1}