Ivan Ivanovich, the evil problemsetter, got tired of you and your team always using Java's BigInteger class. In an attempt to get back at you, he created this problem. You are to write a program which calculates the sum of pairs of integers. Simple, isn't it?

Not so fast, coder. You will be dealing with base36 integers. Haven't you heard of them? It's easy.

• Digits from '0' to '9' represent the values 0 to 9.
• Digits from 'A' to 'Z' represent the values 10 to 35.

So ACMICPC₃₆ is 22531225296₁₀ and UCI2009₃₆ is 66059390601₁₀.

Input

Input starts with an integer T, representing the number of test cases (1<=T<=100). For each test case you will be given two base36 positive integers X1 and X2, whose lengths won't exceed 1000 digits.

Output

Print T sums, no leading zeroes, one line each.

Example

Input:
2
ACMICPC
UCI2009
ACMICPC
UCI2009

Output:
14P4KCPL
14P4KCPL