Island Counting on Thutmus I: Memory Processor Challenge

The ancient pharaohs once sent spacecraft to a distant planet, Thutmus I (now commonly known as Mars). The surface of the planet is modeled as a grid of \( (2n+1) \times (2n+1) \) square cells. Each cell is either land (1) or water (0). Two land cells are considered connected if there exists a path from one to the other that only travels through adjacent land cells (adjacency is defined by sharing a common side). An island is defined as a maximal set of pairwise connected land cells.

The spacecraft uses a very archaic computer whose memory is organized as a \( (2n+1) \times (2n+1) \) array. Each memory cell stores a string of length 100 consisting entirely of the characters 0 and 1. Initially, the 0th character of each string in location \( h[i][j] \) stores the state of the corresponding grid cell \( s[i][j] \) (\( 0 \le i,j \le 2n \)). The remaining characters in each memory cell are set to 0.

Because the computer can only process a 3×3 block of memory at a time—and it can only modify the value at the top‐left cell of that block—a multi‐stage procedure is used. In stage \( k \) (with \( 0 \le k \le n-1 \)), for \( m = 2(n-k-1) \), the machine processes every cell \( (i, j) \) for \( 0 \le i,j \le m \) in row-major order in that stage. In the final stage (\( k = n-1 \)), only cell \( (0,0) \) is processed, and the value written there is expected to be the island count expressed as a binary string. Note: The binary string is formatted such that the least significant bit (LSB) is the first character (index 0), the next bit is at index 1, and so on.

Your task is to simulate the final outcome of this procedure by counting the islands on the planet and outputting the answer as a 100-character binary string in which the LSB is at index 0. In a simplified version of the problem, you are given the grid, and you must compute the island count and then output its binary representation (with the least significant bit first) padded with zeros to a total length of 100 characters.

inputFormat

The first line of input contains an integer \( T \) indicating the number of test cases.

For each test case, the first line contains an integer \( n \) (where \( n \ge 0 \)). The grid then follows as \( (2n+1) \) lines, each containing exactly \( (2n+1) \) characters. Each character is either 0 (water) or 1 (land).

outputFormat

For each test case, output a single line containing a 100-character binary string which represents the number of islands. The binary representation should be written with the least significant bit first. If necessary, pad the binary string with 0 characters to ensure it is exactly 100 characters long.

sample

1
0
1

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000