### 2009 Mock DWITE by A.J.: Problem 2

## The Missing Link...

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

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

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 32323 and 32423, 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.

All Submissions

Best Solutions

**Point Value:** 7

**Time Limit:** 5.00s

**Memory Limit:** 256M

**Added:** Sep 26, 2009

**Author:** amleshjk

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

wangzilv1998on Nov 12, 2013 - 1:22:06 am UTCbbi5291on Nov 12, 2013 - 2:16:59 am UTC Re: ...