Telephone

Time limit1sMemory limit128 MB

Summary

Find the base between 2 and 10 whose representation of N has the fewest adjacent digit changes, breaking ties by the largest base.

Level: Easy2 of 10
Topics: Math, Implementation, Brute force
Solved: No attempts yet

Problem

Memorizing telephone numbers can be tiring. Sometimes it is easier to remember a number in some base other than decimal and convert it back to decimal only when it is needed.

The complexity of a number written in some base is the number of pairs of adjacent digits that differ. For example, the complexity of 123 is 2, and the complexity of 4444 is 0.

Given a number, find the base between 2 and 10 in which its representation has the smallest complexity.

Input

The only line contains a positive integer $N$ with at most ten decimal digits ( $1 \le N \le 9\,999\,999\,999$ ).

Output

Print one integer between 2 and 10: the base in which the representation of $N$ has the smallest complexity. If several bases achieve it, print the largest of them, since the representation in that base is probably the shortest.

Examples2

Example 1
Input
```
255
```
Expected output
```
4
```
Example 2
Input
```
3780666
```
Expected output
```
10
```