At last, an interesting and difficult problem! P69284

Here, we say that a natural $n$ is primeful if it is possible to obtain a prime number by deleting some (possibly none) digits from $n$.

For example, 6814 is primeful because deleting 8 and 4 results in 61, which is prime.

Given several $n$, can you determine whether they are primeful or not?

Input

Input consists of several $n$, all between 1 and $10^{10^5} - 1$.

Output

For every given $n$, tell if it is primeful or not.