Let's call a string , consisting of characters A, B, C alphabetic, if it contains ABC as a subsequence.
You are given a string consisting of characters A, B, C. It's guaranteed that it contains at least one A, at least one B, and at least one C.
In one operation, you can swap any two adjacent characters of the string. What's the smallest number of operations you have to make to make the string alphabetic?
A string is a subsequence of a string if can be obtained from by deletion of several (possibly, zero or all) characters.
The first line of the input contains a single integer (1 \le t \le 5\cdot 10^4). The description of the test cases follows.
The only line of each test case contains a single string (length of doesn't exceed 2\cdot 10^5). It's guaranteed that consists of characters A, B, C and that it contains at least one A, at least one B, and at least one C.
It's guaranteed that the sum of lengths of over all test cases doesn't exceed 2\cdot 10^5.
For each test case, output the smallest number of operations you have to make to make the string alphabetic.
Example 1
In the first test case, string ABC already contains ABC as a subsequence.
In the second test case, it's enough to do two operations: BCA BAC ABC.
In the third test case, it's enough to do three operations: CBA BCA BAC ABC.
In the fourth test case, it's enough to do three operations: CBCBABA CBCABBA CBACBBA CBABCBA.
In the fifth test case, it's enough to do one operation: BAAACCCB BAAACCBC. Note that the resulting string doesn't have to contain ABC as a substring.