전화번호

전화번호를 외우기는 번거롭다. 때로는 번호를 10진법이 아닌 다른 진법으로 외워 두었다가 필요할 때만 10진법으로 바꾸는 편이 더 쉽다.

어떤 진법으로 쓴 수의 복잡도는 서로 다른 인접한 두 자릿수 쌍의 개수로 정의한다. 예를 들어 123의 복잡도는 2이고 4444의 복잡도는 0이다.

자연수 하나가 주어질 때 2진법부터 10진법 중에서 이 수를 쓴 표기의 복잡도가 가장 작은 진법을 구하여라.

첫째 줄에 자연수 $N$이 주어진다. $N$은 10진법으로 최대 10자리이다. ($1 \le N \le 9\,999\,999\,999$)

$N$을 쓴 표기의 복잡도가 가장 작은 진법을 2 이상 10 이하의 정수로 출력한다. 그런 진법이 여러 개이면 그중 가장 큰 진법을 출력한다. 큰 진법일수록 표기가 대체로 짧기 때문이다.