Bizarre Bookkeeping
/
No tags
Problem
Editorial
Analytics

As a security officer, you maintain a system that makes a log on people's entry and exit into the government headquarters of virtualBit. The system writes I (in) if a person enters and O (out) if a person exits. A log is group of such entries (Eg. IOIIOOIO) taken at the end of a day.

But due to some technical faults, some of the log entries in a log flipped (I for O and O for I). A faulty log will make you look bad! So you decided to change the log entries (to make it look like there was no fault). Find the minimum number of flips required to make it look like a valid log entry. Assume that no person stayed in the headquarters at the end of the day.

Examples

1. "IIOOIO" (valid log entry since 2 people entered, 2 exited, 1 entered and 1 exited).

2. "IOOI" (clearly invalid log entry since at the 3rd position in the log only one person entered but 2 people exited).


NOTE: It is ensured that the test cases provided always have the solution. The length of log is always even.

Input

The first line contains T, the number of test cases.

Each test case contains a string S denoting the faulty log at the end of a particular day.

Output

Output the minimum number of flips required to make the log valid.

Constraints

1 <= T <= 5000

1 <= length(S) <= 106

The total length of all strings in a single test file does not exceed 3 * 107

length(S) is even

SAMPLE INPUT
2
IOOO
IOOI
SAMPLE OUTPUT
1
2
Explanation

In the first test case, IOOO can be transformed to IOIO or IIOO to make it a valid log.

In the second test case, IOOI --> IIOO or IOIO. So minimum of 2 flips is required.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...