The Warehouse

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Olya works as a warehouse keeper for a TShirt factory. Now the factory is facing hard times, so currently they produce only the Tshirts of three kinds: red, green and blue TShirts. All the Tshirts are stored in the containers, each of the containers contain the TShirts of a single colour.
Now there are N containers at the warehouse, lined up in a line. Let's enumerate the containers by the positive integers from 1 to N, starting from the leftmost and ending at the rightmost one. Their order is described with a string S. Each symbol of this string is either "r", "g" or "b" and denotes the colour of the respective Tshirts, stored in the container.
Olya likes orderliness. She is not satisfied with the fact that different kinds of containers are messed up. So she wants to rearrange the containers in such a way that the number of pairs of adjacent containers that contain the Tshirts of different colors is as minimal as possible.
For doing that, she has a special crane. The crane is capable of doing the following things:
 Take a container with the number X and put it in front of all the containers. This operation takes (X1) seconds. Note that we are considering the 1dimensional model of the warehouse, so "in front of all the containers" means to the left of all the containers. The warehouse is so large, so you shouldn't worry about its' size and this operation is always performable.
 Take a container with the number X and take some container to the left of it (say, the container number Y). Remove the container number X from its' position and insert it right after the container with the number Y. This operation will take XY1 seconds.
 Take a container with the number X and take some container to the right of it (say, the container number Y). Remove the container number X from its' position and insert it right after the container with the number Y. This operation will take YX seconds.
Note that after the operation, we will reenumerate the containers from left to right by the positive integers from 1 to N.
Though Olya is keen on orderliness, she doesn't way to stay at the warehouse for long on Sunday. So she asks you to help her and to calculate the minimal possible number of seconds that is necessary to rearrange the containers in the desired way.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first (and only) line of each test case contains a string S, consisting of N symbols denoting the color string corresponding to the containers.
Output
For each test case, output a single line containing the answer to the problem's question for the corresponding test case.
Constraints
 1 ≤ T ≤ 10
 The string S consists only of the lowercase Latin letters from the set {r, g, b}.
 (Subtask 1): 1 ≤ N = S ≤ 7  33 points.
 (Subtask 2): 1 ≤ N = S ≤ 1000  33 points.
 (Subtask 3): 1 ≤ N = S ≤ 10^{5}  34 points.
Example
Input: 4 rgr rrr rgb rgbr Output: 1 0 0 2
Explanation
Example case 1.We can move the second container to the beginning of the line. This will take one second.
Example case 2.Containers are already in desired way.
Example case 3.Here also, containers are already in desired way.
Example case 4.You can put first r to the just right of b. It will take 2 seconds to do so.
Author:  xcwgf666 
Tester:  furko 
Editorial  http://discuss.codechef.com/problems/WPROB 
Tags  ltime21, medium, xcwgf666 
Date Added:  24012015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions