Endgame

The chessboard has only a White king, a Black king, and a White rook. It is White's move. Assume the opponent plays optimally and delays defeat as long as possible. Find the minimum number of moves White needs to deliver checkmate.

The rules of chess are summarized in the Hint section. If you already know them, you can skip it. Your chess skill will not help you solve this problem.

The first line contains the number of test cases $z$ ($1 \leq z \leq 10$). Each test case is given as eight lines describing the board. Each line has exactly eight characters: . for an empty square, W for the White king, B for the Black king, and R for the White rook. Each piece type appears exactly once. The starting position is valid: the kings are not adjacent, and the Black king is not under attack. A blank line follows each test case.

For each test case, print one line with one integer: the maximum number of moves White needs to deliver checkmate. Count only White's moves.

Chess rules:

• The players move alternately, one piece per turn.
• A player cannot pass. Every turn, a legal move must be made.
• The king moves one square in any direction: horizontally, vertically, or diagonally.
• The rook moves any number of squares along a row or column, but it cannot jump over other pieces.
• A king is under attack if an opposing piece could move to its square.
• A player may not make a move that puts or leaves their own king under attack. In particular, a king cannot move next to the other king.
• The Black king can move onto the square of the White rook if the White king is not adjacent to the rook. The rook is captured and the game ends in a draw.
• If Black has no legal move, the game ends. It is checkmate (White wins) if the Black king is under attack, or stalemate (a draw) if it is not.
• In the situation described above (king and rook vs. king), checkmate is always possible in less than 50 moves.