Minimal Dial Moves to Unlock the Prime Lock

Turtle has secured his precious item with a password lock consisting of 5 rotating digit dials. Each dial displays a digit. Every rotation moves the current digit by 1. Rotating upward increases the digit by 1 (with 9 rolling over to 0) and rotating downward decreases the digit by 1 (with 0 rolling over to 9).

The 5 digits on the dials form a 5-digit number (leading zeros are allowed). The lock will open if the number formed is a prime number. Recall that a prime number (or 质数) is a natural number greater than \(1\) that is divisible only by \(1\) and itself.

Your task is to help the turtle unlock the safe by determining the minimum total number of moves required to transform the current number into any prime number. For each wheel, you may rotate it either upward or downward. The cost to change one digit from \(d\) to \(t\) is \(\min(|d-t|, 10-|d-t|)\), where \(|d-t|\) denotes the absolute difference between \(d\) and \(t\).

Input Example: If the input is 12345, you need to compute the minimum total moves to transform "12345" into some prime number (for example, changing it to "12347" might cost 2 moves).

Note: The answer must be computed so that the total cost over all 5 digits is minimized.

inputFormat

The input consists of a single line containing a 5-digit number (possibly with leading zeros).

Example: 12345

outputFormat

Output the minimum number of moves required to reach a prime number.

Example: 2

sample

00000

2