덧셈 기호 '+'를 사용해 어떤 수를 한 자리 수로 만들고자 한다.

수를 하나의 문자열로 생각했을 때, 숫자와 숫자 사이 중 한 곳에 덧셈 기호를 삽입할 수 있다.

덧셈 기호가 삽입되면 원래의 수는 덧셈 기호를 사이에 둔, 두 수의 합을 나타내는 식이 된다.

이 식을 계산하여 이전의 수보다 작은 새로운 수를 만들 수 있다.

덧셈 기호를 삽입할 수 없는 한 자릿수가 나올 때까지 이 작업을 반복한다.

아래 예시는 73425를 한 자릿수로 만드는 방법 2가지를 나타낸다.

* 방법 1.

(73425) -> (7 + 3425 = 3432) -> (3 + 342 = 435) -> (4 + 35 = 39) -> (3 + 9 = 12) -> (1 + 2 = 3)

* 방법 2.

(73425) -> (73 + 425 = 498) -> (49 + 8 = 57) -> (5 + 7 = 12) -> (1 + 2 = 3)

위의 2가지 방법 중 두 번째가 덧셈 기호 사용 횟수를 최소로 하여 한 자릿수를 만드는 방법이다.

4회 만에 한 자릿수를 만드는 다른 방법도 있지만,

다른 어떤 방법으로도 4회보다 적은 횟수로 한 자릿수를 만들 수 없다.

그리고 연산 과정이 끝난 후 만들어진 한 자릿수는 3이다.

10억 이하의 자연수 N이 주어진다.

덧셈 기호를 가장 적게 사용해 N을 한 자릿수로 만들 때,

덧셈 기호 사용 횟수 a와 연산 과정 끝에 만들어진

한 자릿수 b를 구하는 프로그램을 작성하시오.

한자리수 만들기 timer 1s memory 256MB

한자리수 만들기 1s 256MB