P1218 [USACO1.5] Superprime Rib

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.

A single line containing a positive integer $n$.

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

Constraints For $100\%$ of the testdata, $1 \le n \le 8$. Problem translation from NOCOW. USACO Training Section 1.5. Translated by ChatGPT 5