El has a string \(S\) consisting of '\(0\)', '\(1\)' and '\(2\)' as only characters. El is a sorted person, so he does not like randomness, so when he looks at the string and finds that characters in string are in random order, he becomes frustrated. He wants to clean up the string, i.e, he wants all same characters in the string to appear together. In one move El can swap any two characters in the string, i.e, he can select index \(i\), \(j\) then swap \(S_i\) and \(S_j\). Find the minimum number of moves required to clean the string.

Input Format

First line contains an integer \(T\), which denotes the number of test cases.
Each line of the test case contains a string \(S\) consisting of '\(0\)', '\(1\)' and '\(2\)' as only characters.

Output Format

For each test case print only one integer - the minimum no. of moves required.

Constraint

\(1 \leq T \leq 10^4 \\ 1 \leq |S| \leq 2 \cdot 10^5 \\ \text{Sum of length of strings for all test case does not exceed} \ 2\cdot10^5\)