Channel is a very important part of a digital communication system．The characteristics of the channel affect the performance of the whole digital communication system．The noise and interference in the real channel make the codes received different from the codes sent．The difference is generally called error．In order to improve the quality of communication and ensure the reliability and validity of communication, error-control coding is usually adopted to correct the errors produced in the process of transfer before the digital signals enter the channel．

Error-control coding is all effective method to enhance the communication quality by adding redundant information into the original message. Convolution code is a kind of error-correcting code which is used very widely. So，as the corresponding best decode method of the convolution codes，Viterbi decoder is always researched widely．

Now, we only want to do some research about the encoding of convolution codes. First we give an example to you to explain the procedure of the encoding:

If we research the encoding of the （2，1，7） convolution codes. And the rate of the convolution codes is 1/2, the construction is the following picture:

The connection parameter is 1011011 and 1111001. So we can define the generation matrix P:

So:

P(1)=[1 0 1 1 0 1 1]

_{P(2)=[1 1 1 1 0 0 1]}

As we all know, the convolution operation( ' ' ) is defined as follows:

For the discrete convolution,

We can know : 

length(Z) = length(X))+ length(Y) – 1;

In this problem we use the binary discrete convolution. When we calculate ,We should also do it like this :

First, do the discrete convolution, then for all the Z(i), Z(i) = Z(i) % 2;

If we give an input A=[1 1 1 0 1 1 1 0 1 1], we need to calculate the output sequence after encoding. As above, the generation matrix has told to you, so We can calculate the answer as follows:

B = AP(1);       C = AP(2);

Then for every B(i) and C(i), you just need do like this

B(i) = B(i) % 2=[1100110001100101];      C(i) = C(i) % 2=[1011110001110011];

The encoding output is [B(1)C(1)B(2)C(2) ……];

In this problem, the generation matrix is unique which is told above, we will give you the input sequence, you will tell us the sequence after encoding.  Pay attention to that all the input and output is 0 or 1 sequence. 

There are plenty of test cases，for each test case ：There is a sequence which contains a series of ‘0’ and ‘1’ in one line. The length of the input sequence is at most 1000 and at least 1.  The end of the input is indicated by the end of the file(EOF).

For each test case , you should output the test case number and the sequence after convolution encoding in a line. The format is like the sample.