All Your Base

Premise. You are given a mixed-radix number system (each digit has its own base). Read pairs of numbers written in this system, apply the requested operation to each pair, and print each result in the same system.

The base. Digits are numbered from the right as $1, 2, \dots$. The $n$-th digit from the right (digit $n$) may hold any value from $0$ to $n$. Digit values $0$ through $9$ are written with the usual characters; values $10$ and above use uppercase letters $A$ (=10) through $Z$ (=35). Because a digit value can never exceed $35$ ($Z$) and digit $n$ is bounded by $n$, a number can have at most 35 digits; anything that would need more is invalid. Negative numbers carry a single leading -. Numbers never have leading zeros, except zero itself, which is the single character 0.

Operations. Addition (+) and subtraction (-) behave exactly like ordinary arithmetic, with carrying and borrowing as needed.

• The first line contains the number of operations to perform, in base 10.
• Each of the following lines is at most 1000 bytes and consists of a number in this system, a space, a single operator character (+ or -), a space, another number in this system, and a newline (LF).
• Either operand, and the result, may be negative.

• For each operation, print one line: either the result written in this number system, or the word Invalid.
• If either operand is not a valid number in this system, or the result of the operation is not a valid number (for example, it would need more than 35 digits), print Invalid.