2009 Mock DWITE by A.J.: Problem 2

Having just learned what primes are in math class, Boxer wants to put this newly acquired skill to the test. Given a number that is missing a digit, help Boxer list all possible digits that makes this number prime.

Input Specification

The input will contain five lines, each containing a string of characters which consists of up to ~6~ characters. Exactly one of these characters will be an underscore (_), while the rest will be digits. The first character in the string will never be the digit zero. This string represents an integer with one missing digit. (The missing digit is represented by the underscore.)

Output Specification

For each line given in input, in the order given, print one line containing a space-separated list of digits sorted in ascending order which can be used to fill in the blank for the missing digit such that the number generated is prime, or the string Not possible if there is no digit which fulfils the requirement.

Sample Input (only three sets shown)

1_
32_23
_46230

Sample Output

1 3 7 9
3 4
Not possible

Explanation

In the first case, there are four primes that can be obtained by filling in the blank: ~11~, ~13~, ~17~, and ~19~, obtained by filling in the blank with the digits ~1~, ~3~, ~7~, and ~9~, respectively.

In the second case, there are two five-digit primes starting with ~32~ and ending with ~23~, and they are ~32\,323~ and ~32\,423~, obtained by filling in the blank with ~3~ and ~4~, respectively.

In the third case, regardless of the digit filling the blank, ~2~ will be a proper factor, so no choice yields a prime number.