The base (or radix) of a positional
numeral system is the number of symbols that can be used to
represent a number in that system. The base $10$ system (also known as decimal)
uses $10$ distinct
symbols: $0, 1, \ldots ,
9$. For example, we interpret the number $72345$ as:
\[ 7 \times 10^4 + 2 \times 10^3 + 3 \times
10^2 + 4 \times 10^1 + 5 \times 10^0. \]
This example illustrates that in base $10$ the symbol at place $P\ge 0$ (starting from the right) is
multiplied by $10^ P$ to
get its value. More generally, in base $B$ we use $B$ symbols to represent $0, \ldots , B1$, and the symbol at
the $P$th place is
multiplied by $B^ P$ to
get its value.
Other bases commonly used in computation include base
$2$ (or binary, using
symbols $0$ and
$1$), base $8$ (or octal, using symbols
$0$–$7$), and base $16$ (or hexadecimal, using symbols
$0$–$9$ and $a$–$f$). In bases higher than
$10$, letters represent
the higher values. Thus in hexadecimal $a$–$f$ represent the decimal values
$10$–$15$, and in bases $\ge 36$ the letter $z$ represents the decimal value
$35$.
Your job is to determine the bases in which given arithmetic
expressions are valid. We define an expression as
valid in base $B$
if two conditions are true. First, all the operands used are
interpretable in base $B$
as having values in the decimal range $[1,2^{32}1]$. Second, the expression
is true. Any arbitrary expression might be valid in zero, one,
or more bases. In this problem we will only consider bases
$1$–$36$, where base $1$ is unary.
Note that following the convention listed above, unary would
consist of a single symbol: $0$. In this problem, unary numbers
use the symbol $1$ rather
than $0$ (think “tally
marks”). E.g., $111$ in
unary is equivalent to the decimal number $3$ and $1111111$ in unary is equivalent to
the decimal number $7$.
Input
Input for this problem starts with a line containing an
integer $0\le N \le 20$.
The following $N$ lines
each contain an arithmetic expression with the following
form:
\[ X ~ op ~ Y ~ = ~ Z
\]
where $X$, $Y$, and $Z$ are positive, whole numbers
consisting of $1$ to
$100$ symbols from the set
$0$–$9$ and $a$–$z$, and $op$ is one of the four operators
+, , *, /. For each statement there is at
least one base $1\le B \le
36$ such that $X$,
$Y$, and $Z$ can all be interpreted in base
$B$ as having values in
the decimal range $[1,2^{32}1]$.
Output
For each expression, list the bases in which the expression
is valid (sorted in ascending base order) or the word “invalid”
if the expression not valid in any of the bases $1$–$36$. Use symbols $1$–$9$, then $a$–$z$, then $0$ to represent bases $1$–$36$ (with the last symbol,
$0$, representing base
$36$).
Sample Input 1 
Sample Output 1 
8
6ef + d1 = 7c0
3 / 2 = 1
444 / 2 = 222
10111 * 11 = 1000101
10111 * 11 = 111221
5k  1z = 46
1111111111  1111111 = 111
2048  512 = 1536

g
invalid
56789abcdefghijklmnopqrstuvwxyz0
2
3456789abcdefghijklmnopqrstuvwxyz0
invalid
1
a
