What Base Is This?#1377

What Base Is This?

1 second

64 megabytes

Medium

In positional notation, the position of a digit determines its weight in the value of a number. For example, in base $10$ , the number $362$ has the digit $2$ with weight $1 0^{0}$ 10^0, $6$ with weight $1 0^{1}$ 10^1, and $3$ with weight $1 0^{2}$ 10^2, giving the value $3 \times 1 0^{2} + 6 \times 1 0^{1} + 2 \times 1 0^{0}$ 3 \times 10^2 + 6 \times 10^1 + 2 \times 10^0, or simply $300 + 60 + 2$ 300 + 60 + 2. The same method applies to numbers in other bases. While most people are used to seeing numbers in base $10$ , other bases are also possible. For example, $362$ in base $9$ or base $14$ has a completely different value than $362$ in decimal.

In this problem, you are given a sequence of pairs of integers. Let's call them $X$ and $Y$ . Your task is to find the smallest base for $X$ and the smallest base for $Y$ (these bases may be different), so that both represent the same value.

For example, consider the pair $12$ and $5$ . These are not equal if both are interpreted as base $10$ . But if $12$ is interpreted in base $3$ and $5$ in base $6$ , $12$ as base $3$ is $1 \times 3^{1} + 2 \times 3^{0} = 5$ 1 \times 3^1 + 2 \times 3^0 = 5, and $5$ in any base is $5$ in decimal. So $12$ and $5$ can be equal if the correct bases are chosen.

Input

Each line contains a pair of integers $X$ and $Y$ , separated by at least one space. Lines may have leading or trailing spaces, which should be ignored. The bases for $X$ and $Y$ can be any integer from $2$ to $36$ inclusive; they do not have to be the same. Digits $0$ – $9$ have their usual values, and uppercase letters $A$ – $Z$ represent values $10$ – $35$ .

Output

For each pair, print a message as shown in the examples, indicating whether $X$ and $Y$ can be equal in some valid bases. If this is not possible, print an appropriate message as shown in the output examples.

Examples

Example

12 (base 3) = 5 (base 6)
15 (base 10) = 15 (base 10)
AB is not equal to 33 in any base 2..36
1 (base 2) = 1 (base 2)
A (base 11) = 9 (base 10)

Example 1