표 4

시간 제한1초메모리 제한512 MB

요약

2 이상 10 이하의 N에 대해 N×N 격자를 만들되, 각 행과 열, 두 주대각선이 읽히는 N자리 수가 모두 M의 배수이고 서로 다르며 0으로 시작하지 않아야 한다.

난이도: 보통10점 중 7점
유형: 백트래킹, 완전 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

정수 $M$ 이 주어졌을 때, $N$ 행 $N$ 열 크기(2 ≤ $N$ ≤ 10)의 정사각형 표를 십진 숫자로 채우려고 한다. 이때 각 행(왼쪽에서 오른쪽), 각 열(위에서 아래), 각 주대각선(위에서 아래)에 있는 숫자로 만든 $N$ 자리 수는 모두 $M$ 의 배수여야 하고, 맨 앞자리가 0이어서는 안 되며, 표 안에서 서로 달라야 한다.

예를 들어 $M = 2$ 에 대한 올바른 표는 다음과 같다.

2 3 4
5 6 6
8 2 0

다음 표는 $M = 2$ 에 대해 올바르지 않다.

$N < 2$ 이기 때문이다.

2 0
4 8

마지막 열과 주대각선 중 하나에 있는 수의 맨 앞자리가 0이기 때문이다.

2 3 4
5 8 8
2 0 2

수 482가 표에 두 번 나오기 때문이다.

이 문제를 항상 풀 수 있는 것은 아니다. 예를 들어 $M = 10$ 인 경우에는 답이 없다.

입력

첫째 줄에 $M$ 의 값이 하나 주어진다.

출력

첫째 줄에 표의 행과 열의 개수 $N$ 을 출력한다. 그다음 $N$ 개 줄에 걸쳐 $i$ 번째 줄(1 ≤ $i$ ≤ $N$ )에는 표의 $i$ 번째 행의 원소 $N$ 개를 공백으로 구분해 출력한다.

제한

$M = 45$

힌트

주어지는 각 테스트 입력에 대해 답이 적어도 하나 존재한다는 것이 알려져 있다.

예제1

예제 1
입력
```
2
```
예상 출력
```
3
2 3 4
5 6 6
8 2 0
```