Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Now a days, Roy is chilling with his friends. But suddenly, He got an idea to create a problem. Problem is very simple,

Given a string S, your task is to transform S into a "beautiful" string. A beautiful string is defined as a string in which no two identical characters are separated by any other characters. In other words, all instances of a particular character must be grouped together. Your goal is to rearrange the characters in S to meet this criterion.

For example : S = "ABCABC"

all valid beautiful string from S = "AABBCC" , "BBAACC" , "CCAABB" , "AACCBB","BBCCAA" , "CCBBAA" etc.

You can do following of the operation :

In each operations you can select two indicies i and j, 1 <= i,j <= |S|, swap their character.(Ex. swap( S[i], S[j])).

Find minimum operations need to make S beautiful.

Input

First Line contains T, the number of test case.
In each test case, a string S.
\(1 <= T <= 10^4\)
\(1 <= | S | <= 10^5\)
String S contains only English uppercase letter A,B,C.

It is guranteed that the length of string S overall test case doesn't exceed \(2 * 10^5\).

Output

In each test case print the minimum operation required.

Sample

2
ABCCBA
ABAC

1
1

First test case, intially string S= "ABCCBA".

if you swap indices 2 and 6, string S become "AACCBB" , which is beautiful.

So only 1 operation required.