다이얼 자물쇠

다이얼 자물쇠는 숫자가 인쇄된 여러 개의 다이얼을 가진 자물쇠의 일종이다. 이 자물쇠에는 해제 순열이라는 특별한 숫자열이 있어야 열 수 있다.

여러분은 다이얼 자물쇠 제조사에서 일한다. 여러분의 임무는 생산된 모든 자물쇠가 해제 순열로 열리는지 검사하는 것이다. 다시 말해, 수많은 자물쇠의 수많은 다이얼을 돌려야 한다.

이 일은 매우 어렵고 지루하다. 여러분은 자물쇠를 여는 데 걸리는 시간을 줄이고 싶다. 여러 다이얼을 한 번에 돌리는 것이 좋은 방법이다. 하지만 주어진 자물쇠를 최소 횟수의 회전으로 여는 방법을 찾는 것은 어려운 문제다. 그래서 여러분은 초기 순열과 해제 순열이 주어졌을 때 그러한 방법을 찾는 프로그램을 작성하기로 했다.

여러분 회사의 다이얼 자물쇠는 수직으로 쌓인 k (1 ≤ k ≤ 10)개의 원통형 다이얼로 이루어져 있다. 각 다이얼에는 원통 옆면을 따라 왼쪽에서 오른쪽으로 0부터 9까지의 숫자 10개가 순서대로 인쇄되어 있다. 9의 오른쪽 이웃은 0이다.

다이얼은 특정 위치에서 한 숫자를 가리킨다. 다이얼을 왼쪽으로 i칸 돌리면 다이얼은 오른쪽으로 i번째 숫자를 새로 가리킨다. 반대로 다이얼을 오른쪽으로 i칸 돌리면 왼쪽으로 i번째 숫자를 가리킨다. 예를 들어 8을 가리키는 다이얼을 왼쪽으로 3칸 돌리면 다이얼은 1을 새로 가리킨다.

여러분은 인접한 다이얼 여러 개를 한 번에 돌릴 수 있다. 예를 들어 다이얼 5개가 있는 자물쇠를 생각해 보자. 2번째 다이얼만 돌릴 수 있다. 3번째, 4번째, 5번째 다이얼을 동시에 돌릴 수도 있다. 하지만 2번째 다이얼을 돌리지 않고 1번째와 3번째 다이얼을 한 번에 돌릴 수는 없다. 여러 다이얼을 돌릴 때는 같은 방향으로 같은 칸만큼 돌려야 한다.

여러분의 프로그램은 초기 순열과 해제 순열이 주어졌을 때 자물쇠를 열기 위한 최소 회전 횟수를 계산해야 한다. 인접한 다이얼 하나 이상을 같은 방향으로 같은 칸만큼 돌리는 것을 회전 한 번으로 센다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 두 줄로 이루어진다. 첫째 줄에는 정수 k가 주어진다. 둘째 줄에는 초기 순열과 해제 순열을 나타내는 두 문자열이 공백으로 구분되어 주어진다.

마지막 데이터셋 다음에는 0 하나가 있는 줄이 온다. 이 줄은 어떤 데이터셋에도 속하지 않으며 처리해서는 안 된다.

각 데이터셋마다 최소 회전 횟수를 한 줄에 출력한다.