Binary Addition

Interview

Time limit1sMemory limit128 MB

Summary
Add two binary strings up to length 80 for multiple test cases and print the sum without leading zeros.
Level

Easy2 of 10

Topics
String, Simulation, Math
Solved
No attempts yet

Problem

Adding binary numbers works much like adding decimal numbers. Process the digits from right to left, and keep track of the carry while adding each column.

For binary addition, the only rules you need are the following five cases.

  • 0 + 0 = 0
  • 1 + 0 = 1
  • 0 + 1 = 1
  • 1 + 1 = 10
  • 1 + 1 + 1 = 11

Given two binary numbers, write a program that prints their sum in binary.

Input

The first line contains T, the number of test cases. (1 <= T <= 1,000)

Each test case contains two binary numbers separated by whitespace. Each binary number consists only of the characters 0 and 1, and its length is at most 80. The sum may have 81 digits. A binary number may begin with 0.

Output

For each test case, print the sum of the two input binary numbers in binary. Do not print unnecessary leading zeros.

Examples1

  1. Example 1

    Input
    3
1001101 10010
1001001 11001
1000111 1010110
    Expected output
    1011111
1100010
10011101