Game of Life

Conway's Game of Life is a famous simulation based on very simple rules that produces cool patterns. The goal of this challenge is to simulate the Game of Life.

Game Rules

Based on Wikipedia

Game of Life is played on a 2D grid of "cells", where each cell can be alive or dead. In this challenge, the live cells never reach the edge of the grid. Every cell interacts with its 8 surrounding neighbors. At each turn, the following transitions should occur:

• Any live cell with fewer than two live neighbors dies (as if from under-population).
• Any live cell with two or three live neighbors lives on to the next generation.
• Any live cell with more than three live neighbors dies (as if by overcrowding).
• Any dead cell with exactly three live neighbors becomes a live cell (as if by reproduction).

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths occur simultaneously. The rules continue to be applied repeatedly to create further generations.

Input

Boilerplate code is provided to scan the input into a 2D array.
The first line of input contains t, the number of test cases. t cases follow.
The first line of each test case contains n for the size of the grid.
A n * n grid follows of space-separated numbers, which consists of a 0 for each non-live cell and a 1 for each live cell.

Output

Print out the first 15 stages of the game of life, starting from the first generation. After printing each grid, print the tilde symbol (~) on its own line. Don't print out the the initial grid of input (the 'seed'). You can use the provided helper method to print out the board.

Sample Input

1
20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output

The first step of output should look like this:

0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000001110000000
0000001010000000
0000001110000000
0000001110000000
0000001110000000
0000001110000000
0000001010000000
0000001110000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
~

The remaining output should go through this pattern:

"I-Column" by TastedWasted.
Licensed under CC BY-SA 4.0 via Wikimedia Commons.