You are given ~T~ strings ~S_1, S_2, \dots, S_T~ 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

~1 \le T \le 4 \times 10^4~

~5 \le |S_i| \le 2 \times 10^5~, where ~|S_i|~ denotes the number of characters in ~S_i~.

The sum of the lengths of the ~T~ strings does not exceed ~2 \times 10^5~.

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 ~T~ strings does not exceed ~10~.

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer ~T~, the number of strings.

The ~i^\text{th}~ of the next ~T~ lines contains a string ~S_i~.

Output Specification

On the ~i^\text{th}~ line output a single integer, the minimum number of operations required to make bruce a substring of ~S_i~.

Sample Input

3
buncher
bestcomputerprogrammingteacher
bruce

Sample Output

7
15
0