Reconstruct the Prime

Alice wrote a prime number on a piece of paper. The next day, she found that some parts of the number were smudged. A prime number is a natural number greater than 1, which has no positive divisors other than 1 and itself, i.e. a number n such that for all divisors d (with 1 < d < n), d does not divide n.

You are given a string that consists of digits and '*' characters. The '*' character represents a damaged digit whose value is unknown. Your task is to replace each '*' with a digit (0-9) such that the resulting number is a prime. If there are multiple solutions, output the smallest prime (in numerical value). If no valid prime can be obtained, output -1.

Note on replacements: If the first character is '*', it cannot be replaced by 0, as the number should not have any leading zeros.

Example: If the input is 1*, the possible primes could be 11, 13, 17, 19. The smallest among these is 11, so the output should be 11.

inputFormat

The input consists of a single line containing the string representing the partially obscured prime number.

outputFormat

Output the smallest prime number that matches the pattern. If there is no valid prime, output -1.

sample

1*

11