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
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.
