숫자 자물쇠 2

다이얼 N개가 한 줄로 놓인 숫자 자물쇠가 있다. 다이얼마다 0부터 9까지의 숫자가 차례대로 적혀 있고, 그중 하나가 보인다.

다이얼을 위로 돌리면 보이는 숫자가 0에서 1로, 1에서 2로 바뀌고, 9는 0으로 돌아간다. 아래로 돌리면 반대 방향으로 바뀐다.

다이얼 여러 개를 한꺼번에 돌릴 수 있다. 이때 함께 돌리는 다이얼은 서로 붙어 있어야 하고, 모두 같은 방향으로 한 칸씩 움직인다. 개수에는 제한이 없다. 이렇게 한 번 돌리는 것을 한 번으로 센다.

예를 들어 자물쇠가 123이면, 모든 다이얼을 아래로 돌려 012를, 모두 위로 돌려 234를, 가운데 다이얼만 위로 돌려 133을, 앞의 두 다이얼을 아래로 돌려 013을 한 번에 만든다. 224는 한 번 돌려서 만들지 못한다.

현재 자물쇠의 상태 S와 맞춘 상태 T가 주어질 때, S를 T로 만드는 데 필요한 최소 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 S가, 둘째 줄에 T가 주어진다. 두 문자열의 길이는 같고, 1 이상 2500 이하이다. 각 문자는 0부터 9까지의 숫자이며 맨 앞에 0이 올 수 있다.

첫째 줄에 S를 T로 만들기 위해 다이얼을 돌려야 하는 횟수의 최솟값을 출력한다.