Oswald and Daisy are discussing on the topic of strings. Daisy has a question in her mind and asked Oswald to solve it for her. If Oswald could solve it, then Daisy would buy him an ice-cream. But Oswald is unable to solve it because he is weak in strings.

The string consists of only 'a', 'b' or 'c' (in lower-case). Daisy asked Oswald to make all the characters of the string equal to any of the above 3 characters in minimum number of steps.

She defines one step to be as follows - In one step, a letter (for example - 'a') can make its adjacent letter(s) the same as it is (i.e. 'a'). Also, if there are many occurrences of this letter (i.e. 'a') in the string, all of them can make their adjacent letter(s) equal to this letter (i.e. 'a') in ONE STEP.

Can you help Oswald so that he can get the ice-cream by solving the question ?

Input:
First line consists of test case (t), followed by a line-break. Then 't' lines follow, each consisiting of a string containing only 'a', 'b' or 'c' (in lower-case).

Output:
Print 't' lines (for all test cases), i.e. the answer for the above question.

Constraints:
10 points :
1<= t <= 20
1<= (size of string) <= 500
90 points :
1<= t <= 20
1<= (size of string) <= 500000

Problem Setter
Devesh Jagwani