Let a and b be two 31-bit binary num- bers. Consider the following method for computing a + b. Let c, d be 31-bit numbers such that: • ci =1ifai ̸=bi • ci = 0 if ai = bi • di =1ifai =bi =1 • di =0ifai =0orbi =0 Now, replace a with c and b with 2∗d and repeat these steps until either b=0orb≤231. Intheformercase, 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 The first number indicates the number of test cases. Each test case consists of two 31-bit numbers a and b. Output 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 231 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 ≤ 231. 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

2/2 1100000000000000000000000000000 0100000000000000000000000000000 1000000000000000000000000000000 1000000000000000000000000000000 0000000000000000000000000000000 overflow