RSI: 두 손가락 숫자 입력

당신의 목표는 세계에서 가장 빠른 두 손가락 타이피스트가 되는 것입니다. 이 문제에서는 숫자 문자열을 입력할 때 두 손가락의 이동을 최적화하여, 주어진 숫자를 가능한 한 짧은 시간에 모두 입력하는 것이 목표입니다. 숫자 키패드의 배치는 다음과 같습니다.

7 8 9
4 5 6
1 2 3
0 0

각 칸은 (행, 열)로 나타냅니다. 예를 들어 '5' 키는 (2, 2)에 있습니다. '0' 키는 크기가 커서 (4, 1)과 (4, 2) 두 칸을 모두 차지하며, 두 위치 중 어느 곳을 눌러도 '0'이 입력됩니다. (4, 3) 위치에는 키가 없습니다.

시각 0에서 왼손 검지는 '4' 키(위치 (2, 1))에, 오른손 검지는 '5' 키(위치 (2, 2))에 놓여 있습니다. 매 단위 시간마다 각 손가락은 다음 중 하나를 독립적으로 할 수 있습니다: 바로 아래의 키를 누르기, 세로로 한 칸 이동, 가로로 한 칸 이동(제자리에 머무를 수도 있습니다). 두 손가락은 같은 단위 시간에 동시에 움직일 수 있지만, 다음 조건을 지켜야 합니다.

• 한 단위 시간에는 최대 하나의 키만 누를 수 있습니다.
• 매 단위 시간이 끝나는 시점에 왼손 손가락의 열은 항상 오른손 손가락의 열보다 엄격히 작아야 합니다.
• 매 단위 시간이 끝나는 시점에 두 손가락은 모두 10개의 키 중 하나 위에 있어야 합니다(예를 들어 어떤 손가락도 (4, 3) 위에 있을 수 없습니다).

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 1자 이상 100자 이하의 숫자로 이루어진 한 줄의 문자열입니다. 입력은 'eof'라는 단어가 적힌 줄로 끝나며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 주어진 숫자들을 순서대로 입력하는 데 필요한 최소 단위 시간을 한 줄에 하나씩 출력합니다.

• '56'을 입력하는 데는 3단위 시간이 걸립니다. 첫 단위 시간에 두 손가락이 각각 오른쪽으로 한 칸 이동하여 '5'와 '6' 위에 놓이고, 그 다음 두 키를 차례로 누릅니다.
• '71'을 입력하는 데는 5단위 시간이 걸립니다. 왼손 손가락이 위로 올라가 '7'을 누르는 데 2단위 시간이 걸립니다. 그런데 오른손 손가락은 왼손 손가락과 같은 열에 있을 수 없으므로 '1'은 왼손 손가락만 누를 수 있고, 따라서 왼손 손가락이 '1'로 내려가는 데 2단위 시간, 누르는 데 1단위 시간이 걸립니다.