Rank and File

Chess-playing programs have existed almost as long as computers themselves; in 1997 IBM's Deep Blue defeated world champion Garry Kasparov. Every such program must be able to recognize a decisive position — a checkmate. Given the current layout of a chessboard, decide for the side that is about to move whether its king is safe, in check, or checkmated.

Chess is played on a board of $8 \times 8$ squares. Square colors are irrelevant here; the board is treated as a uniform grid.

Two sides, white and black, oppose each other. For this problem each side uses only five kinds of pieces — king, queen, rook, bishop, and knight (there are no pawns). The sides alternate, moving exactly one piece per turn; a side may never skip a turn.

The pieces move as follows:

• Rook: any number of squares in a straight line along a rank or file (the four horizontal and vertical directions).
• Bishop: any number of squares in a straight line along a diagonal (the four diagonal directions).
• Queen: any number of squares in a straight line in any of the eight horizontal, vertical, and diagonal directions.
• Knight: jumps to a square two steps in one cardinal direction and one step perpendicular to it — up to eight destination squares. A knight is never blocked by intervening pieces.
• King: one square in any of the eight directions (any immediately adjacent square).

A piece may move onto an empty square, or onto a square holding an opposing piece, which is then captured and removed. A piece may not move onto a square holding a friendly piece. Every piece except the knight slides across the board, so any piece — friendly or enemy — in its path blocks all further movement in that direction.

The king cannot be captured, but it can be threatened. When an opposing piece could capture the king on the next move, the king is in check. A side in check must respond by moving the king to safety, blocking the threat with another piece, or capturing the threatening piece; a side may never leave its own king in check. If the side to move is in check and has no legal move that removes the check, it is checkmated and loses.

No other chess rules (such as castling or en passant) apply. Each board holds exactly one white king and exactly one black king; either side may have any number of rooks, bishops, queens, and knights.

The first line contains a single integer $D$ ($1 \le D \le 100$), the number of data sets. Each data set consists of:

• One line with a single character naming the side to analyze — the side about to move. A lowercase w means white; an uppercase B means black.
• Eight lines of eight characters each, describing the board from top to bottom. Each character is one of:
  • . — an empty square;
  • a lowercase r, b, q, n, or k — a white rook, bishop, queen, knight, or king;
  • an uppercase R, B, Q, N, or K — the same pieces for black.

For each data set, print one line. Start it with WHITE IS or BLACK IS , matching the analyzed side, then append CHECKED if that side's king is in check, CHECKMATED if it is checkmated, or SAFE if neither holds.

Only the five listed pieces and the movement rules above are used: there are no pawns and no special moves. The colors of individual squares do not matter, and the side to analyze is always the side about to move.