Prime Square

A prime square is a 5×5 grid, each cell holding a single digit, such that all of the following are five-digit primes: the five rows (each read left to right), the five columns (each read top to bottom), and the two diagonals (both read left to right, i.e. in the direction of increasing column). The main diagonal is read from the top-left cell to the bottom-right cell, and the anti-diagonal is read from the bottom-left cell to the top-right cell.

For example, the grid below is a prime square.

1 1 3 5 1
3 3 2 0 3
3 0 3 2 3
1 4 0 3 3
3 3 3 1 1

We want to find every prime square satisfying all of the following conditions.

• The digit sums of all twelve primes (rows, columns, and diagonals) must be equal, and this common digit sum is given in the input. (It is 11 in the grid above.)
• The digit in the top-left cell (row 1, column 1) is fixed and given in the input. (It is 1 in the grid above.)
• The same prime may appear more than once within a single prime square.
• A five-character string starting with 0 is not a five-digit prime. For example, 00003 is not a five-digit prime.

Find all prime squares satisfying these conditions.

The first line contains the digit sum that every prime must have.

The second line contains the digit placed in the top-left cell of the prime square.

Print every prime square satisfying the conditions. Print each prime square over 5 lines, 5 characters per line, and separate consecutive prime squares by one blank line.

When there are several prime squares, sort them in ascending lexicographic order by the 25-character string formed by concatenating the rows from the first to the last, and print them in that order. If no prime square satisfies the conditions, print nothing.