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