Determine the Base

Problem Background

Special for beginners, ^_^

Problem Description

$6 \times 9 = 42$ is wrong in decimal, but correct in base $13$, i.e.

$$6_{13} \times 9_{13} = 42_{13}$$

and

$$42_{13} = 4 \times 13^1 + 2 \times 13^0 = 54_{10}$$

Your task is to write a program that reads three integers $p$, $q$, and $r$, then determines a base $B\ (2 \le B \le 16)$ such that $p \times q = r$. If there are multiple choices for $B$, output the smallest one. For example: $p = 11, q = 11, r = 121$. Then

$$11_3 \times 11_3 = 121_3$$

because

$$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}$$

For base $10$, we have

$$11_{10} \times 11_{10} = 121_{10}$$

In this case you should output $3$. If no suitable base exists, output $0$.

Input Format

One line containing three integers $p$, $q$, $r$, separated by single spaces. All digits of $p$, $q$, $r$ are decimal digits, and $1 \le p, q, r \le 1{,}000{,}000$.

Output Format

One integer: the smallest $B$ such that $p \times q = r$ holds. If no suitable $B$ exists, output $0$.

Sample Input

6 9 42

Sample Output

13

Constraints

1s, 1024KiB for each test case.