Description

Farmer John’s cows always produce the best ribs. You can recognize them by the numbers stamped on each rib by Farmer John and the USDA.

Farmer John is sure he sells genuine superprime ribs because, starting from the right and removing one rib at a time, the digits on the ribs that remain always form a prime number.

For example: for $7\ 3\ 3\ 1$, the digits of all ribs $7331$ form a prime; with three ribs $733$ it is still prime; with two ribs $73$ it is prime; and, of course, the last rib $7$ is also prime. $7331$ is called a superprime of length $4$.

Write a program that, given the number of ribs $n$, finds all superprimes of length $n$. $1$ is not a prime.

Input Format

A single line containing a positive integer $n$.

Output Format

Output, in increasing order, all superprimes of length $n$, one per line.

4

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 8$.

Problem translation from NOCOW.
USACO Training Section 1.5.

Translated by ChatGPT 5