import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class GraphNode { public Point point; public int distance; public GraphNode(Point p, int d) { this.point = p; this.distance = d; } } class Point { public int x; public int y; public Point(int x, int y){ this.x = x; this.y = y; } @Override public boolean equals(Object other) { Point otherPoint = (Point) other; return otherPoint.x == x && otherPoint.y == y; } @Override public int hashCode() { int result = x; result = 31 * result + y; return result; } } public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] matrix = solveKnightL(n); for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-1; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } public static int[][] solveKnightL(int n) { int[][] matrix = new int[n-1][n-1]; //int i = 3, j = 4; for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { ArrayList dx = new ArrayList(); ArrayList dy = new ArrayList(); dx.add(i); dy.add(j); dx.add(i); dy.add(j * -1); dx.add(i * -1); dy.add(j); dx.add(i * -1); dy.add(j * -1); dx.add(j); dy.add(i); dx.add(j); dy.add(i * -1); dx.add(j * -1); dy.add(i); dx.add(j * -1); dy.add(i * -1); //(x + 2, y + 1) //(x + 2, y - 1) //(x - 2, y + 1) //(x - 2, y - 1) //(x + 1, y + 2) //(x + 1, y - 2) //(x - 1, y + 2) //(x - 1, y - 2) matrix[i-1][j-1] = solveKnightL(n, dx.toArray(new Integer[8]), dy.toArray(new Integer[8])); //return matrix; } //return solveKnightL(n, dx.toArray(new Integer[8]), dy.toArray(new Integer[8])); } //int[] dx = {2, 2, -2, -2, 1, 1, -1, -1}; //int[] dy = {-1, 1, 1, -1, 2, -2, 2, -2}; return matrix; } public static int solveKnightL(int n, Integer[] dx, Integer[] dy) { Point source = new Point(0, 0); Point destination = new Point(n-1, n-1); Queue q = new LinkedList(); Map m = new HashMap(); q.add(new GraphNode(source, 0)); while (!q.isEmpty()) { GraphNode node = q.remove(); Point point = node.point; int distance = node.distance; if (point.x == destination.x && point.y == destination.y) { return distance; } if (m.containsKey(point)) continue; m.put(point, true); for(int i = 0; i < 8; ++i) { int x1 = point.x + dx[i]; int y1 = point.y + dy[i]; if (valid(x1, y1, n)) q.add(new GraphNode(new Point(x1, y1), distance + 1)); } } return -1; } private static boolean valid(int x, int y, int N) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } }