Baltic Olympiad in Informatics: 2003 Day 1, Problem 3

For the given integer $M$, build a square table with $N$ rows and $N$ columns, filled with decimal digits, with the following restriction: the $N$-digit numbers formed by the digits in each table row (from left to right), each table column (from top to bottom) and each main diagonal (from top to bottom) must be multiples of $M$, must not start with the digit $0$ and must be unique within the table.

For example, a valid table for $M=2$ is:

$${\displaystyle \begin{array}{|ccc|}\hline 2& 3& 4\\ 5& 6& 6\\ 8& 2& 0\\ \hline\end{array}}$$

The following tables are not valid for $M=2$:

• $\begin{array}{|c|}\hline 4\\ \hline\end{array}$ because $N<2$;

• $\begin{array}{|cc|}\hline 2& 0\\ 4& 8\\ \hline\end{array}$ because the numbers in the last column and on one of the main diagonals start with the digit $0$;

• $\begin{array}{|ccc|}\hline 2& 3& 4\\ 5& 8& 8\\ 2& 0& 2\\ \hline\end{array}$ because the number $482$ is present twice in the table.

It is not always possible to solve this task. For example, the task is unsolvable for $M=10$.

Constraints

$2\le N\le 10$

Each cell value must be an integer between $0$ and $9$.

Input Specification

The input contains one integer $t$ $(1\le t\le 10)$, denoting the number of the current test case.

The input for these ten test cases are found as text files in the attachment below. Each test case file will contain one integer $M$.

For example, if $t=3$, the input for this test can be found in the file 3.in.

Output Specification

Output a valid table for test case $t$. This table is guaranteed to exist. The first line of output must contain $N$, the number of rows and columns in the table. The $(i+1{)}^{\text{th}}$ line of the file $(1\le i\le N)$ must contain the elements of the $i^{\text{th}}$ row of the table as $N$ space-separated digits.

Grading

You will score $0$ points for a test case if there is no output for this test case or if any of the conditions given above are not met.

Otherwise your score for the test case is calculated from the formula:

$${\displaystyle \lfloor 10\times \frac{\text{Reference solution's }N}{\text{Your solution's }N}\rfloor }$$

Therefore, you should try to find a valid table with the least possible size, within the conditions given above.

Sample Input

0

Sample Output

3
2 3 4
5 6 6
8 2 0

Sample Explanation

The input contains $0$, denoting this case's input data can be found in the file 0.in. 0.in contains one integer $2$, which means you should output a valid table for $M=2$.

This table size is not minimized and thus wouldn't yield full points. Note that $1\le t\le 10$, this is just the sample case.

Attachment Package

The input files are available here.