PKU 2845. 01000001

01000001

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 5031	Accepted: 1654

설명

이진수를 더하는 것은 매우 쉬운 일이며, 일반적인 십진수의 덧셈과 매우 유사합니다. 십진수를 더할때와 같이, 당신은 한 번에 한 줄에 있는 비트(아라비아 숫자)들을 오른쪽에서 왼쪽으로 씁니다. 십진수끼리의 덧셈과는 달리, 이진수들을 더할때에 기억해야 할 것이 몇가지 있습니다 :

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

십진수의 덧셈과 같이, 한 줄에 더해진 총합이 두 자리 비트(두 자리 수)일 경우 의미가 적은 숫자는 총 합의 부분으로 쓰여지고 의미가 큰 숫자는 왼쪽 줄로 '옮겨집니다'. 다음 예시를 확인하세요:

                       11  1 <-- Carry bits  --> 1   11
  1001101             1001001                    1000111
+ 0010010           + 0011001                  + 1010110
 --------           ---------                  ---------
  1011111             1100010                   10011101

왼쪽의 덧셈 문제는 각 줄의 합이 10이나 11이 아닌 1이나 0이기 때문에 옮겨지는 비트가 없습니다. 다른 두 문제에서는 옮겨지는 비트가 명백히 존재하지만, 더하는 과정은 여전히 간단합니다.

입력

입력할 첫번째 행은 하나의 정수 N (1 ≤ N ≤ 1000)으로 시작하는데, 이 N은 밑에 나올 이진수의 합을 구하는 문제들의 수를 나타냅니다. 각 문제는 한 행에 두 개의 이진수 값을 주는데,  두 이진수는 한 칸의 공백을 사이에 두고 나타내어집니다. 각 이진수의 최대 길이는 80 비트(이진수)입니다.
주의사항: 결과값의 최대 길이는 81비트(이진수)가 될 수 있습니다.

출력

각 이진수의 합 문제에서, 문제의 번호를 표시하고 그 다음 공백을 둔 뒤 합해진 이진수의 결과를 나타냅니다. 앞쪽에 나오는 0들은 생략하세요.

입력 예시

3
1001101 10010
1001001 11001
1000111 1010110

출력 예시

1 1011111
2 1100010
3 10011101

Source

Greater New York 2005