Captures in One Move

A chess board with pieces on it is given. Count the different ways in which any piece can be captured in one move. Colors do not matter in this problem, so any piece captures any other piece as long as the move is legal.

A square is written as one letter and one digit: A1, A2, ..., A8, B1, ..., H8. The letter runs from A to H and the digit runs from 1 to 8.

The pieces move like this.

• (K) A king moves one square in any of the eight directions.
• (Q) A queen moves any number of squares in any of the eight directions, but cannot jump over another piece.
• (R) A rook moves only horizontally or vertically, and cannot jump over another piece.
• (B) A bishop moves only diagonally, and cannot jump over another piece.
• (N) A knight moves two squares in one direction and then one square at a right angle to it, jumping over anything in between.
• (P) A pawn captures only by moving diagonally toward the higher letter (A to B, B to C, and so on). A pawn on the square with letter $c$ and digit $r$ attacks exactly the two squares whose letter is the one after $c$ and whose digit is $r-1$ or $r+1$.

A queen, a rook and a bishop stop on the first occupied square along a direction, so each of them captures only the nearest piece in that direction.

Count the ordered pairs (capturing piece, captured piece). With a king on B2, a pawn on A1 and a queen on H8 the answer is 3. The queen on H8 captures the king on B2, the pawn on A1 captures the king on B2, and the king on B2 captures the pawn on A1.

The first line has the number of test cases $T$. Each test case starts with a line holding the number of pieces $N$, followed by $N$ lines that each give one piece in the form square-type. For example, A1-K means a king on A1. The type is one of K, Q, R, B, N, P, and no two pieces share a square. Blank lines may appear between test cases.

Limits

• $1 \le T \le 100$
• $1 \le N \le 64$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of different ways in which a piece can be captured in one move.