12953번 - 숫자 자물쇠 2

총 N개의 다이얼로 이루어져 있는 숫자 자물쇠가 있다. 각각의 다이얼은 0부터 9까지의 수가 순서대로 적혀져 있다.

각 다이얼에 보이는 숫자는 다이얼을 위나 아래로 돌리면서 바꿀 수 있다. 다이얼을 위로 돌리면 0이 1로, 1이 2로, ..., 9가 0으로 돌아가게 된다. 다이얼은 아래로 돌리면 반대 방향으로 돌아가게 된다.

다이얼 여러 개를 동시에 돌릴 수 있다. 이때, 다이얼은 모두 연속해 있어야 하며, 개수의 제한은 없다.

예를 들어, 현재 자물쇠가 123 이라면, 모든 다이얼을 아래로 돌려서 012를 만들거나, 모든 다이얼을 위로 돌려서 234를, 가운데 다이얼을 위로 돌려서 133, 처음 두 다이얼을 아래로 돌려서 013을 만들 수 있다. 224는 다이얼을 한 번 돌려서 만들 수 없는 경우이다.

현재 자물쇠의 상태 S와 자물쇠를 맞춘 상태 T가 주어졌을 때, S를 T로 만들기 위해 다이얼을 돌려야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 S가, 둘째 줄에 T가 주어진다. S와 T의 길이는 같고, 2500을 넘지 않는 자연수이다.

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