import java.io.*; import java.util.*; import java.util.stream.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static class Point { int x; int y; Point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Point point = (Point) o; if (x != point.x) return false; return y == point.y; } @Override public int hashCode() { int result = x; result = 31 * result + y; return result; } } static class Vertex { Point point; int distance = Integer.MAX_VALUE; Vertex(Point point) { this.point = point; } List getAdjacents(Map vertices, int moveX, int moveY) { List adjacents = new ArrayList<>(); adjacents.add(vertices.getOrDefault(new Point(point.x + moveX, point.y + moveY), null)); adjacents.add(vertices.getOrDefault(new Point(point.x + moveX, point.y - moveY), null)); adjacents.add(vertices.getOrDefault(new Point(point.x - moveX, point.y + moveY), null)); adjacents.add(vertices.getOrDefault(new Point(point.x - moveX, point.y - moveY), null)); adjacents.add(vertices.getOrDefault(new Point(point.x + moveY, point.y + moveX), null)); adjacents.add(vertices.getOrDefault(new Point(point.x + moveY, point.y - moveX), null)); adjacents.add(vertices.getOrDefault(new Point(point.x - moveY, point.y + moveX), null)); adjacents.add(vertices.getOrDefault(new Point(point.x - moveY, point.y - moveX), null)); return adjacents.stream().filter(vertex -> vertex != null).collect(Collectors.toList()); } } public static Map shortestPath(Map vertices, int moveX, int moveY) { Vertex source = vertices.get(new Point(0, 0)); source.distance = 0; PriorityQueue minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.distance)); Map distanceMap = new HashMap<>(); Map parentMap = new HashMap<>(); for (Vertex vertex : vertices.values()) { minHeap.add(vertex); } distanceMap.put(source, 0); parentMap.put(source, null); while(!minHeap.isEmpty()) { Vertex current = minHeap.poll(); if (current.distance == Integer.MAX_VALUE) { break; } distanceMap.put(current, current.distance); for (Vertex adjacent : current.getAdjacents(vertices, moveX, moveY)) { if (!minHeap.contains(adjacent)) { continue; } int newDistance = distanceMap.get(current) + 1; if (adjacent.distance > newDistance) { minHeap.remove(adjacent); adjacent.distance = newDistance; minHeap.add(adjacent); parentMap.put(adjacent, current); } } } return distanceMap; } public static int compute(int n, int moveX, int moveY) { if (moveX == n - 1 && moveY == n - 1) { return 1; } Map vertices = new HashMap<>(); for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { Point point = new Point(x, y); vertices.put(point, new Vertex(point)); } } Map distanceMap = shortestPath(vertices, moveX, moveY); Vertex target = vertices.get(new Point(n - 1, n - 1)); return distanceMap.getOrDefault(target,-1); } public static void main(String... args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for (int x = 1; x < n; x++) { for (int y = 1; y < n; y++) { System.out.print(compute(n, x, y)); System.out.print(" "); } System.out.println(); } } }