o-and-z-task-for-oz

Today little Oz is in a great mood and wants to solve a programming task, but he doesn't have one! So, he asked his friend Finley. Finley being an experienced programmer, took a paper and wrote a classical challenge for Oz. The following is the challenge set by Finley :

"Given a string S consisting of letters 'O' and 'Z'. Calculate the minimum number of changes required such that all O's are adjacent to each other and all Z's are adjacent to each other. One change is equivalent to swapping two neighbouring letters."

Little Oz needs your help to complete this task as it is too difficult for him to solve alone

Input :

The first line contains T - the number of test cases . Each test case consists of a string S  consisting of characters 'O' and 'Z' only.

Output :

For each test case output the required answer.

Constraints:

1 ≤ T ≤ 10

1 ≤ |S| ≤ 10^6

SAMPLE INPUT
1
OOZOZO

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: EASY


Solutions: