Cannon's Move

Janggi is a Korean board game similar to chess. Two players face each other on a board of size 9 by 10. Each side has 16 pieces of 7 types: 1 king, 2 chariots, 2 cannons, 2 horses, 2 elephants, 2 guards, and 5 pawns. The cannon is special: it both moves and captures by jumping over exactly one other piece along a straight line.

In this problem we play a one-dimensional janggi on a single row of cells. There are four kinds of pieces:

• C (cannon) and F (friend) are your pieces.
• E (enemy) and K (king) are the opponent's pieces.

Empty cells are written as B. Exactly one C and exactly one K appear on the board. Your task is to capture K using a sequence of valid cannon moves.

The rules of one-dimensional janggi are:

1. You may move only C.
2. C moves by jumping over exactly one piece, which may be K, E, or F.
3. C must land either on an empty cell or on a cell holding an opponent's piece (E or K).
4. When C lands on an opponent's piece, we say it captures that piece, and the captured piece is removed from the board. C can never land on (capture) a friendly piece F.
5. The game ends the moment C captures K.

For example, on the board above C sits at position 6. From there C can move to 2 (capturing E), 3, 4, 9, or 10 (capturing E). No other cell is reachable in a single move.

After C captures the E at 10, the board becomes the one shown above. Now C can move to 6, 7, 12, or 13 (capturing K).

Input is read from standard input. The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string that describes a one-dimensional janggi board. Occupied cells are written as C, E, F, or K, and empty cells are written as B. Each string has length at least 5 and at most 200.

Write to standard output. For each test case, print on its own line the minimum number of moves C needs to capture K. If capturing K is impossible, print 0.