Description

A number system is a method of counting with carry. We commonly use the decimal system, which carries over when reaching ten. A base-$K$ system carries over when reaching $K$. In a base-$K$ system, each digit position can only contain numbers from $0$ to $K-1$. For example, binary only uses $0$ and $1$, ternary uses $0$, $1$, and $2$, and decimal uses $0$ through $9$.
For bases greater than 10, we use letters to represent digits: $A$ represents 10, $B$ represents 11, $C$ represents 12, and so on.
Given a positive integer in string form, determine the minimum base in which this number can appear.

Input Format

A single line containing a string of length not exceeding $10^5$, consisting only of digits and uppercase letters, with no leading zeros.

Output Format

A single line containing an integer representing the minimum base in which this number can appear.

Sample

31

4