РАВЕНСТВО

Interview

Time limit1sMemory limit1024 MB

Summary

Given an expression X+Y=Z written in an unknown base, find the smallest base in which the equality holds.

Level: Medium4 of 10
Topics: Math, Brute force, Implementation, String matching
Solved: No attempts yet

Problem

After learning about numeral systems in computer science class, the teacher suggested the following game to the students. One student comes up with an equality of the form X+Y=Z, and the others have to determine which numeral system it is written in.

For example, the equality 1+1=10 is true in binary, and the equality 2B+15A=184 is true in base 17.

Todor does not like calculating by hand at all, so he asks you to write a program equality that finds the base of the numeral system in which the given equality is true.

Input

The first line of the standard input contains a string with an expression of the form X+Y=Z, where X, Y and Z are natural numbers written in some numeral system.

Output

On a single line of the standard output, the program must print one integer: the base of the numeral system. If several answers are possible, the program must print the smallest base of a numeral system in which the equality is true.

Constraints

2 ≤ base of the numeral system ≤ 36
Each of the numbers X, Y and Z has at most 9 digits.
The digits of the numbers X, Y and Z can be the digits '0' to '9', as well as the uppercase Latin letters 'A' to 'Z'.

Hint

Explanation of example 2: In numeral systems with a base greater than 10, the digits 0 to 9 are not enough to write a number, so letters are used for digits greater than 9. Thus, after the digit 9 comes the letter «А», then «В», and so on.

Examples3

Example 1
Input
```
1+1=10
```
Expected output
```
2
```
Example 2
Input
```
2B+15A=184
```
Expected output
```
17
```
Example 3
Input
```
2+2=4
```
Expected output
```
5
```