You are given strings
consisting of lowercase letters. In one operation, you may swap any two adjacent characters in a string. For each string, compute the minimum number of operations required to make
bruce
a substring of that string.
Constraints
, where
denotes the number of characters in
.
The sum of the lengths of the strings does not exceed
.
Each string has at least one occurrence of each of the characters b
, r
, u
, c
, and e
.
Subtask 1 [20%]
The sum of the lengths of the strings does not exceed
.
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line contains an integer , the number of strings.
The of the next
lines contains a string
.
Output Specification
On the line output a single integer, the minimum number of operations required to make
bruce
a substring of .
Sample Input
3
buncher
bestcomputerprogrammingteacher
bruce
Sample Output
7
15
0
Comments