Table 4

Time limit1sMemory limit512 MB

Summary

Build an N by N grid of digits (2 <= N <= 10) so every row, column, and main diagonal reads as a distinct N-digit multiple of M with no leading zero.

Level: Medium7 of 10
Topics: Backtracking, Brute force, Implementation, Math
Solved: No attempts yet

Problem

Given an integer $M$ , build a square table with $N$ rows and $N$ columns (2 ≤ $N$ ≤ 10) filled with decimal digits, subject to 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

2 3 4
5 6 6
8 2 0

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

because $N < 2$ ;

2 0
4 8

because the numbers in the last column and on one of the main diagonals start with the digit 0;

2 3 4
5 8 8
2 0 2

because the number 482 appears twice in the table.

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

Input

The first line contains one value of $M$ .

Output

The first line must contain $N$ , the number of rows and columns in the table. The $i$ -th of the following $N$ lines (1 ≤ $i$ ≤ $N$ ) must contain the elements of the $i$ -th row of the table as $N$ digits, separated by spaces.

Constraints

$M = 45$

Hint

It is known that at least one solution exists for each given test input.

Examples1

Example 1
Input
```
2
```
Expected output
```
3
2 3 4
5 6 6
8 2 0
```