회문 계수기 돌리기

"누가 손을 댔군!" 디들리 위젯의 창업자이자 사장인 J.R. 디들리가 소리쳤다.

"장난은 맞는데 부서진 곳은 없습니다." 회계 책임자 로버트 래키가 답했다.

두 사람은 공장 바닥 위에 매달린 커다란 계수기를 올려다보고 있었다. 공장이 문을 연 날부터 조립 라인에서 나온 위젯 개수를 빠짐없이 세어 온 계수기였다. 그런데 누군가 표시된 숫자를 바꿔 놓았다.

"회문입니다." 래키가 말했다. "앞에서 읽으나 뒤에서 읽으나 똑같습니다."

"내가 모르겠는 건," 디들리가 말했다. "순찰 도는 경비원이 왜 범인을 못 잡았느냐는 거야. 한 칸씩 눌러서 이 숫자까지 가려면 몇 시간은 걸렸을 텐데."

"아닙니다." 래키가 답했다. "위젯이 하나 만들어질 때마다 맨 오른쪽 자리만 올라가긴 하지만, 어느 자리 바퀴든 직접 돌릴 수 있습니다. 계획만 잘 세우면 몇 초면 충분합니다."

바퀴 $k$개로 이루어진 계수기를 생각하자. 각 바퀴는 0부터 9까지의 숫자 하나를 보여준다. 바퀴 하나를 한 번 돌리면 그 자리의 숫자가 다음 숫자로 넘어간다. 예를 들어 3에서 4로, 8에서 9로 넘어간다.

9에서 0으로 넘어가는 것도 가능하다. 다만 이때는 바로 왼쪽 바퀴도 자동으로 다음 숫자로 넘어간다. 이 올림은 왼쪽으로 연달아 이어지기도 하지만, 전부 한 번의 조작 안에서 일어난다. 맨 왼쪽 바퀴에는 왼쪽 이웃이 없으므로, 그 바퀴가 9에서 0으로 넘어가면 올림은 그대로 사라진다.

계수기의 현재 상태가 주어질 때, 회문에 도달하기까지 필요한 최소 조작 횟수를 구하라. 회문은 앞자리 0까지 그대로 따진다. 예를 들어 0011은 회문이 아니다.

입력이 610인 경우를 보자. 6이 있는 바퀴를 네 번 돌리면 010이 되므로 네 번이면 된다.

첫째 줄에 자릿수가 $1$ 이상 $40$ 이하인 정수 하나가 주어진다. 입력의 자릿수가 계수기의 바퀴 개수다. 앞자리에 0이 올 수 있다.

회문을 만드는 데 필요한 최소 바퀴 조작 횟수를 한 줄에 출력한다.