Problem C: Parallel Carry Adder

Let a and b be two 31-bit binary numbers. Consider the following method for computing a+b. Let c,d be 31-bit numbers such that:

• c_i = 1 if a_i ≠ b_i
• c_i = 0 if a_i = b_i
• d_i = 1 if a_i = b_i = 1
• d_i = 0 if a_i = 0 or b_i = 0

Now, replace a with c and b with 2*d and repeat these steps until either b = 0 or b ≥ 2³¹. In the former case, the resulting value of a is the sum of the original numbers. In the latter case, the sum of the original numbers requires 32 bits to express so we say that an overflow has occurred.

Your task is to print the results of all intermediate calculations and report if an overflow occurs.

Input Format

The first number indicates the number of test cases. Each test case consists of two 31-bit numbers a and b.

Output Format

The output for each test case is a series of lines. The first line consists of a and b written in binary and separated by a space. Following this, each line consists of the resulting values of a and b when one iteration of the algorithm is applied to the values in the previous line. Again, these should be written in binary and separated by a space. If any of these numbers has value at least 2³¹ then the message "overflow" should be printed in place of the number. The last line of output to be printed corresponds to the iteration when either b = 0 or b ≥ 2³¹. The output for consecutive input cases should be separated by a blank line.

Sample Input

2
0000000000010000000101011101011 1000010110000110000000111111111
1100000000000000000000000000000 0100000000000000000000000000000

Sample Output

0000000000010000000101011101011 1000010110000110000000111111111
1000010110010110000101100010100 0000000000000000000000111010110
1000010110010110000101011000010 0000000000000000000001000101000
1000010110010110000100011101010 0000000000000000000010000000000
1000010110010110000110011101010 0000000000000000000000000000000

1100000000000000000000000000000 0100000000000000000000000000000
1000000000000000000000000000000 1000000000000000000000000000000
0000000000000000000000000000000 overflow