Picture Puzzle

This kind of picture puzzle is made of nine square pieces. Every edge of a piece carries one half of a picture.

There are four pictures, labelled B, C, K and P. Each picture is cut down the middle into a left half and a right half, so every edge shows one of eight labels: BL, BR, CL, CR, KL, KR, PL, PR. Here XL is the left half and XR is the right half of picture X. A left half fits together with the right half of the same picture:

• BL fits BR
• CL fits CR
• KL fits KR
• PL fits PR

The goal is to place the nine pieces into a 3×3 grid so that, for every pair of side-by-side pieces, the two touching edges fit — that is, they are the two halves of one picture (the same letter, one L and one R). A piece may be rotated by 0°, 90°, 180° or 270° before it is placed. Rotating a piece cyclically shifts its four edge labels around the piece; it never turns an L half into an R half and never changes a letter.

An example puzzle.

One valid arrangement of the pieces.

The input is a sequence of puzzles. Each puzzle begins with its puzzle number on a line by itself. A puzzle number of 0 marks the end of the input and is not a puzzle.

The puzzle-number line is followed by nine lines describing the pieces. Each of these lines contains the piece number (1 through 9) followed by the labels on the piece's top, right, bottom and left edges, in that order, separated by spaces. Every label is one of BL, BR, CL, CR, KL, KR, PL, PR.

For each puzzle, print one line: the puzzle number, a colon, a space, and the number of valid arrangements.

A valid arrangement is a way to place all nine pieces into the 3×3 grid, using each piece exactly once and choosing one of its four rotations, so that every pair of touching edges fits. Count every such arrangement; two arrangements are counted separately even when one is a whole-board rotation of the other. If the puzzle cannot be solved, the count is 0.