Elementary Automaton

Prepare for the contest by creating a simple cellular automaton!

A Cellular Automaton is a model of a grid of 'cells' that change over time based on the patterns of nearby cells.

The objective of this challenge is to create an Elementary Automaton, or a 1-dimensional version of changing cells. Given a starting string of 1's and 0's can you determine the next steps for the Automaton?

Challenge Details

To determine the next step for a given cell, simply look at the cell and its two immediate neighbors. In this challenge, follow a famous pattern known as Rule 110:

For example, if given a string "111", the middle cell will turn into a "0", as shown in the first column of the above table.

The right (and far-left) sides of the string are considered 0's and are not shown in the input or output. This means the string
0 1 1 1 will become:
1 1 0 1
Hover above to see the "pattern" that caused each cell above.

In each case, you will be given an input string to start with and a number b. Can you output the next b steps of the Automaton?

Input Format

You will be given a number t followed by t lines. Each line will contain 2 numbers: a, the starting pattern for the automaton, and b, the number of lines of the pattern to output.

The provided boilerplate code will provide both a and b as integers to the method doStuff.

Output Format

For each test case, output the specified number of lines of the pattern (including the starting string).

For this challenge, always print out the same length string. To do this, print out b 0's along with the given input and decrease the leading 0's by 1 on each line.

Sample Input/Output

Input

1
1 15

Output

0000000000000001
0000000000000011
0000000000000111
0000000000001101
0000000000011111
0000000000110001
0000000001110011
0000000011010111
0000000111111101
0000001100000111
0000011100001101
0000110100011111
0001111100110001
0011000101110011
0111001111010111