B. Make it ODOO!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's party time at Odoo! These Odooers... they sure know how to party! However, as any mortal human being, they are having trouble setting up the printer for decorations.

The printer was supposed to print a nice big ODOO strip, but, instead, it printed a scrambled sequence of O's and D's, even with more letters than needed. For instance, it just now printed ODODODODODO...

The party organization committee is now going to fix the strip, making it a proper ODOO, but following the operations bellow:

  • Removing a letter: Since it's a strip, they can only cut out a letter from the beginning or the end, not from the middle. They can't remove more than one letter at a time.
  • Transforming a letter: O's and D's are quite similar, so they can transform an O into a D and vice-versa.

Being the clever bunch they are, the Odooers want to fix the strip as quickly as possible. How many minutes will it take them at the least? Both operations above have the same cost of 1 minute to be done.

Input

The first line of the input contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ indicating the number of test cases.

Each of the following $$$T$$$ lines contains a string $$$S$$$ $$$(4 \leq |S| \leq 10^3)$$$ of upper-case O's and D's in any order.

Output

Print the minimum amount of minutes needed to transform $$$S$$$ into ODOO following the operations described in the statement.

Example
Input
6
ODOO
DODOOD
ODODO
DDDDDDDDD
DODODODO
OODO
Output
0
2
2
8
5
2