Background

The renowned mathematician John H. Conway (1937–2020) sadly passed away during the COVID-19 pandemic. His research interests spanned multiple fields, including combinatorial game theory and group theory, and he made significant contributions to the classification of finite groups, cellular automata, and combinatorial games. He was dedicated to the popularization of mathematics and designed "Conway's Game of Life," which became a global phenomenon.

Today, let us revisit one of his most famous inventions.

The rules of the Game of Life are as follows:

1. There is a square grid where each cell has a state: dead or alive. The state of each cell at the next time step is uniquely determined by its current state and the states of its 8 neighbors.
2. If a cell is currently alive and has fewer than 2 living neighbors, it becomes dead.
3. If a cell is currently alive and has 2 or 3 living neighbors, it remains in its current state.
4. If a cell is currently alive and has more than 3 living neighbors, it becomes dead.
5. If a cell is currently dead and has exactly 3 living neighbors, it becomes alive; otherwise, it remains dead.

Description

Due to computer memory limitations, we cannot simulate the Game of Life on an infinite grid. Therefore, we only consider the Game of Life on a $4\times 4$ grid, assuming that cells outside the grid are always dead.

You are given $Q$ queries. For each query, you are given the state of each cell on a $4\times 4$ grid. You need to determine the state of each cell on the grid after $T$ time steps.

Input

The input is read from standard input.

The first line contains a positive integer $Q$, representing the number of queries.

The following $5Q$ lines contain the queries, with 5 lines per query.

For each query, the first 4 lines each contain a string of length 4 consisting of 0s and 1s, representing the state of the cells in the grid, where 0 represents dead and 1 represents alive. The next line contains a positive integer $T$, representing the number of time steps that pass.

Output

The output is written to standard output.

Output $4Q$ lines, with 4 lines per query representing the answer.

For each query, the answer consists of 4 lines, each containing a string of length 4 consisting of 0s and 1s, representing the state of the cells in the grid, where 0 represents dead and 1 represents alive.

Examples

1
0000
1100
0110
0000
3

0100
1010
1010
0100

After one time step, the grid state becomes:

0000
1110
1110
0000

After another time step, the grid state becomes:

0100
1010
1010
0100

The next state will be the same as this one, meaning it will remain in this state for all subsequent time steps. Therefore, after 3 time steps from the start, the grid is in this state.

See ex_2.in and ex_2.ans in the download directory.

Subtasks

For $100\%$ of the data, it is guaranteed that $Q \le 10^{4}$ and $T \le 10^{9}$.

Time and Memory Limits

Time limit: 1.0 second Memory limit: 256 MB