You just received a call from NASA's chief scientist who is working on a habitable structure to be built on the moon. He has designed various models of enclosed cities that people could live in, but he is unsure as to how these models will stand up to population growth. Therefore, since your name has become synonymous with "He Can Program Anything From Neat, Flashy Space Games That Entangle You For Hours To Highly Sophisticated Super Spy Surveillance Satellite Image Enhancement Algorithms," he immediately called you with his problem. Here is what he said:

"I need a program which will read in a set of data points that represent the location of living quarters within the city. I then want the program to simulate the creation, growth, and death of each living quarter per year based on the following rules:

1. Every living quarter with two or three neighboring quarters survives the current year.
2. Each living quarter with four or more neighbors dies due to over-population. Each living quarter with one or less neighbors dies from isolation.
3. Each empty location that is adjacent to exactly three neighbors - no more, no fewer - will have someone build new living quarters in that location for the next year.

Note that each living quarter can have from zero to eight adjacent neighbors (i.e. north, south, east, west, north-west, north-east, south-west, and south-east) at any given time.

Input and Output

Each city model will have a maximum of 20 possible living quarters in the north-south direction and 20 in the east-west direction. The top left corner will be designated location 1,1 (N-S position, E-W position) and the bottom right is therefore 20,20. I want the program to read the data file and then output the existing population map for each year. Year 1 will correspond to the initial configuration. Therefore, the first map in the file should be the initial configuration. Mark empty locations with a space and living quarters with a capital letter O.

Please separate each year's output with a single line of 20 asterisks, and put a similar line both as the first and the last of the output file. Any questions?"

"Yes, one," you replied, "What will the input file look like?

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

"Let the first line of each input specify the number of years to run the simulation. Then, following that will be the coordinates for the initial locations. 

 The outputs of two consecutive cases will be separated by a blank line.

Oh, by the way, I need this to be completed within the next four hours. Talk to you later. Bye."

Sample Input

1

3
5 4
5 5
5 6
5 7

Sample Output

********************
 
 
 
 
   OOOO
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
********************
 
 
 
    OO
    OO
    OO
 
 
 
 
 
 
 
 
 
 
 
 
 
 
********************
 
 
 
    OO
   O  O
    OO
 
 
 
 
 
 
 
 
 
 
 
 
 
 
********************

輸出比較麻煩，他描述不是很清楚，不用刪除 O 之後的空白。
仍然是測資組間空一行。

#include <stdio.h>
#include <string.h>

int cntP(int x, int y, int g[][21]) {
    int i, j, cnt = 0;
    int tx, ty;
    for(i = -1; i <= 1; i++) {
        for(j = -1; j <= 1; j++) {
            tx = x+i, ty = y+j;
            if(tx < 0 || ty < 0 || tx >= 20 || ty >= 20)
                continue;
            if(i == 0 && j == 0)
                continue;
            cnt += g[tx][ty];
        }
    }
    return cnt;
}
int main() {
    int t;
    scanf("%d", &t);
    while(getchar() != '\n');
    while(getchar() != '\n');
    char asterisk[] = "********************";
    char s[50];
    while(t--) {
        gets(s);
        int Y, g[2][21][21] = {};
        int x, y, i, j, k, roll = 0, pre;
        sscanf(s, "%d", &Y);
        while(gets(s) && s[0]) {
            sscanf(s, "%d %d", &x, &y);
            g[roll][--x][--y] = 1;
        }
        puts(asterisk);
        for(i = 0; i < Y; i++) {
            for(j = 0; j < 20; j++, puts("")) {
                for(k = 0; k < 20; k++) {
                    if(g[roll][j][k]) {
                        putchar('O');
                    } else
                        putchar(' ');
                }
            }
            memset(g[1-roll], 0, sizeof(g[roll]));
            for(j = 0; j < 20; j++) {
                for(k = 0; k < 20; k++) {
                    int f = cntP(j, k, g[roll]);
                    if(g[roll][j][k]) {
                        if(f == 2 || f == 3)
                            g[1-roll][j][k] = 1;
                    } else {
                        if(f == 3)
                            g[1-roll][j][k] = 1;
                    }
                }
            }
            puts(asterisk);
            roll = 1-roll;
        }
        if(t)
            puts("");
    }
    return 0;
}