Giải bài trực tuyến

Nếu là một người ưa phát minh, chắc hẳn bạn sẽ cảm thấy thế giới năm 1000003 vô cùng nhàm chán. Lúc này, tất cả mọi phát minh mà con người từng mơ ước tới đều đã trở thành hiện thực. Ô tô bay, nhà bay, thành phố bay... đã xuất hiện nhiều nhan nhản. Tất cả mọi người sống trong những ngôi nhà thông minh được điều khiển bởi giọng nói, ánh mắt hoặc suy nghĩ, với sự hỗ trợ của các hệ thống máy tính hiện đại nhất. Con người có thể di chuyển tức thời giữa không gian (giữa các hành tinh ở cách nhau hàng nghìn năm ánh sáng) và thời gian - điều này đã góp phần khiến cho dân số thế giới tăng với tốc độ chóng mặt, vượt qua con số 1000¹⁰⁰⁰ vào năm 1000003.

Lúc này, những chiếc SmartPhone đã trở nên lỗi thời, do chúng không chịu được áp lực quá lớn khi đi qua cổng dịch chuyển tức thời hoặc khi đi vào các cỗ máy thời gian. Tất cả mọi người đều dùng điện thoại Nokia.

Do dân số thế giới đã tăng vượt mốc 1000¹⁰⁰⁰, những dãy số điện thoại cũng đã dài tới hàng trăm nghìn chữ số. Điều này đã khiến cho việc bấm phím số điện thoại trở nên ác mộng. Trước tình trạng này, hãng điện thoại Nokia đã đưa ra tính năng mới, cho phép bạn có thể thay đổi vị trí các phím số trên bàn phím, để bạn có thể bấm số điện thoại một cách nhanh nhất có thể.

Thời gian để bạn bấm số điện thoại bằng tổng thời gian di chuyển của ngón tay bạn giữa các phím số liên tiếp trong dãy số. Thời gian này đúng bằng khoảng cách Manhattan giữa 2 phím số: Nếu phím số A ở dòng i, cột j, và phím số B ở dòng u, cột v, thì khoảng cách Manhattan giữa 2 phím số được tính theo công thức:

dist(A, B) = |i - u| + |j - v| 

Chẳng hạn, bạn muốn gọi số 357468, nếu sử dụng bàn phím cổ điển:

bạn sẽ mất tổng thời gian là;

dist(3, 5) + dist(5, 7) + dist(7, 4) + dist(4, 6) + dist(6, 8)

= ( |1 - 2| + |3 - 2| ) + ( |2 - 3| + |2 - 1| ) + ( |3 - 2| + |1 - 1| ) + ( |2 - 2| + |1 - 3| ) + ( |2 - 3| + |3 - 2|)

= 2 + 2 + 1 + 2 + 2

= 9

Nhưng nếu bạn thay đổi vị trí các phím số như hình dưới:

thì bạn chỉ mất tổng thời gian là:

dist(3, 5) + dist(5, 7) + dist(7, 4) + dist(4, 6) + dist(6, 8)

= 1 + 1 + 1 + 1 + 1

= 5

Chú ý: Bạn chỉ được phép đổi chỗ các phím số, nghĩa là sau khi bạn thay đổi các phím số, mỗi phím phải tương ứng với duy nhất 1 số, và mỗi số phải tương ứng với duy nhất 1 phím. Các phím phải nằm đúng ở 10 vị trí chứa các số 0-9 trong bàn phím cổ điển. Các phím trên điện thọai được đánh số hàng từ trên xuống dưới, đánh số cột từ trái sang phải (xem ví dụ).

Input

Gồm 1 dòng duy nhất chứa dãy số điện thoại

Output

Gồm 1 dòng duy nhất ghi thời gian nhỏ nhất để bạn bấm dãy số điện thoại, sau khi đã thay đổi vị trí các phím số một cách hợp lý

Giới hạn

• Độ dài dãy số điện thoại không quá 400,000
• Trong 20% số test, độ dài dãy số điện thoại không quá 625

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:
357468

Output:
5