All about that base

The base (or radix) of a positional numeral system is the number of symbols the system uses to write a number. Base 10, also called decimal, uses 10 distinct symbols: 0, 1, ..., 9. For example, the number 72345 is read as

$7 \times 10^4 + 2 \times 10^3 + 3 \times 10^2 + 4 \times 10^1 + 5 \times 10^0$

In base 10 the symbol at place $P \ge 0$, counting from the right, is multiplied by $10^P$ to get its value. In general, base $B$ uses $B$ symbols for the values $0$ through $B-1$, and the symbol at place $P$ is multiplied by $B^P$.

Other bases common in computing are base 2 (binary, symbols 0 and 1), base 8 (octal, symbols 0 to 7), and base 16 (hexadecimal, symbols 0 to 9 and a to f). In bases above 10, letters stand for the larger values. In hexadecimal a to f mean the decimal values 10 to 15, and in base 36 the letter z means the decimal value 35.

Decide which bases a given arithmetic expression holds in. An expression is valid in base $B$ when both of the following are true.

• Every operand, read in base $B$, has a value in the decimal range $[1, 2^{32} - 1]$.
• The expression is true. Division / is true only when it comes out even, with no remainder.

An expression may be valid in no base, in one base, or in several. This problem considers only bases 1 to 36, where base 1 is unary.

Applying the rule above literally, unary would use the single symbol 0. Here unary uses the symbol 1 instead, the way tally marks work. Unary 111 is decimal 3, and 1111111 is decimal 7.

The first line has the number of expressions $N$ $(0 \le N \le 20)$. Each of the next $N$ lines holds one arithmetic expression in this form.

X op Y = Z

$X$, $Y$, and $Z$ are positive whole numbers written with 1 to 100 symbols from the set 0 to 9 and a to z, and op is one of +, -, *, /. For every expression there is at least one base $B$ $(1 \le B \le 36)$ in which $X$, $Y$, and $Z$ all have values in the decimal range $[1, 2^{32} - 1]$.

For each expression print one line listing the bases the expression is valid in, in increasing order of base. Print invalid if the expression holds in no base from 1 to 36. Write bases 1 to 9 as the symbols 1 to 9, bases 10 to 35 as a to z, and base 36 as 0.