The Game of Efil

Almost anyone who has taken a computer science class knows the Game of Life, John Conway's cellular automaton whose very simple rules of birth, survival, and death can produce astonishing complexity.

The game is played on a rectangular grid of cells, each with eight neighbors (the adjacent cells). A cell is either occupied (alive) or empty (dead). Each generation is derived from the previous one by these rules:

• An occupied cell with 0, 1, 4, 5, 6, 7, or 8 occupied neighbors dies (0 or 1: from loneliness; 4 through 8: from overcrowding).
• An occupied cell with two or three occupied neighbors survives into the next generation.
• An empty cell with exactly three occupied neighbors becomes occupied (a birth).

A well-studied question is the existence of "Garden of Eden" configurations: configurations that cannot arise by applying the rules to any previous configuration. We extend this into the "Game of Efil": given a configuration, how many configurations could have preceded it — that is, how many possible parent configurations does it have? To keep the grid finite, it is treated as a torus: the top and bottom edges wrap around to each other, and so do the left and right edges.

When counting the neighbors of a cell, another cell may be counted more than once if the wrap-around makes it adjacent on more than one side, and on a very small grid a cell can even be its own neighbor. Every such occurrence is counted.

There are several test cases. Each case begins with a line containing two positive integers m and n: the number of rows and columns of the configuration. The next line contains a nonnegative integer k, the number of occupied (live) cells. Each of the following k lines contains the row and column of one live cell, with rows and columns numbered starting from zero. The input ends with a line where m = n = 0, which must not be processed. You may assume that the product of m and n is at most 16.

For each test case, print one line with the case number and the number of possible parent configurations, in the form Case X: N possible ancestors., where X is the case number (starting from 1) and N is the count. If a configuration has no possible parent, print Case X: Garden of Eden. instead.