자물쇠 공략하기

여행 가방에 $K$개의 다이얼로 이루어진 숫자 자물쇠가 달려 있습니다. 각 다이얼에는 $0$부터 $9$까지의 숫자가 하나씩 표시되므로, 자물쇠의 모든 설정은 $K$자리 수로 나타낼 수 있습니다(맨 앞의 $0$도 그대로 유지되며 자릿수에 포함됩니다). 이 중 오직 하나의 설정만이 자물쇠를 엽니다.

당신은 정교한 난수 생성기로 비밀 설정을 골랐지만, 그만 그 값을 잊어버렸습니다. 다이얼을 아무렇게나 돌리는 대신, 가능한 모든 설정을 차례대로 시도하기로 합니다. 운이 나쁘게도 정답 설정은 항상 가장 마지막에 시도하는 설정입니다.

한 번의 동작으로는 다이얼 하나를 한 칸 돌려 그 다이얼의 숫자를 정확히 $1$만큼 바꿀 수 있습니다. 다이얼을 $0$에서 $9$로(또는 그 반대로) 곧바로 넘길 수는 없으며, 이 경우에는 $9$번의 동작이 필요합니다. 매 동작 뒤에 현재 설정이 정답인지 확인할 수 있습니다. 처음 설정은 정답이 아님이 알려져 있으므로, 그 설정에서 출발합니다.

처음 설정이 주어졌을 때, 그 설정에서 출발하여 나머지 모든 $K$자리 설정을 각각 적어도 한 번씩 시도하기까지 필요한 최소 동작 횟수를 구하세요.

입력은 여러 개의 인스턴스로 이루어집니다. 각 인스턴스는 처음 설정을 나타내는 십진수 $N$ 하나가 적힌 줄입니다. $N$에는 맨 앞에 $0$이 올 수 있으며, 이 $0$도 자릿수 $K$에 포함됩니다($1 \le K \le 7$). 예를 들어 007은 $3$자리 설정입니다. 마지막 인스턴스 다음 줄에는 -1이 주어집니다.

각 인스턴스에 대해, 최소 동작 횟수 $S$를 한 줄에 출력하세요. 즉 주어진 설정에서 출발하여 나머지 모든 $K$자리 설정을 각각 적어도 한 번씩 시도하기까지 필요한, 다이얼을 한 칸 돌리는 동작의 최소 횟수입니다.