Base Multiplication Puzzle

You are given three integers (p), (q), and (r) represented in string format. Determine the minimum base (B) (where (2 \le B \le 16)) such that the following equation holds true when the numbers are interpreted in base (B):

[ p \times q = r ]

When interpreted in base (B), each digit of (p), (q), and (r) must be less than (B). The value of a number (d_nd_{n-1}\ldots d_0) in base (B) is defined as:

[ \sum_{i=0}^{n} d_i \times B^i ]

If there are several bases satisfying the condition, output the smallest one. If no such base exists, output 0.

Example:
For (p = 11), (q = 11), (r = 121), we can interpret them in base 3 as follows:
(11_{(3)} = 1 \times 3^1 + 1 \times 3^0 = 4_{(10)}) and (121_{(3)} = 1 \times 3^2 + 2 \times 3^1 + 1 \times 3^0 = 16_{(10)}). Since (4 \times 4 = 16), base 3 is a valid solution. Even though base 10 is also valid ((11_{(10)} \times 11_{(10)} = 121_{(10)})), you must output 3 because it is the smallest valid base.

inputFormat

Input consists of a single line containing three strings (without spaces) representing the integers (p), (q), and (r) separated by spaces. Each string is composed of digits (and possibly uppercase letters) representing a number in some base.

outputFormat

Output a single integer (B) ((2 \le B \le 16)) if there exists a base such that when (p), (q), and (r) are interpreted in base (B), the equation (p \times q = r) holds. If there is no such base, output 0.

sample

6 9 42

13