import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private static void addPointToQueue(int x, int y, int count, int n, Map visited, Queue processing) { if ((x >= 0) && (x < n)) { if ((y >= 0) && (y < n)) { Point point = new Point(x, y); if (visited.get(point) == null) { processing.add(new PointAndCount(point, count)); } } } } private static int computeNrMovementsToTarget(int a, int b, int n) { Map visited = new HashMap<>(); Queue processing = new LinkedList<>(); processing.add(new PointAndCount(new Point(0, 0), 0)); while (!processing.isEmpty()) { PointAndCount currPoint = processing.remove(); if ((currPoint.point.x == (n - 1)) && (currPoint.point.y == (n - 1))) { return currPoint.count; } if (visited.get(currPoint.point) == null) { visited.put(currPoint.point, true); addPointToQueue(currPoint.point.x - a, currPoint.point.y - b, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x - a, currPoint.point.y + b, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x + a, currPoint.point.y - b, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x + a, currPoint.point.y + b, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x - b, currPoint.point.y - a, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x - b, currPoint.point.y + a, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x + b, currPoint.point.y - a, currPoint.count + 1, n, visited, processing); addPointToQueue(currPoint.point.x + b, currPoint.point.y + a, currPoint.count + 1, n, visited, processing); } } return -1; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] solutions = new int[n][n]; // Compute solutions for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { solutions[i][j] = computeNrMovementsToTarget(i + 1, j + 1, n); solutions[j][i] = solutions[i][j]; } } // Print solutions for (int i = 1; i < n; ++i) { for (int j = 1; j < n; ++j) { System.out.print(solutions[i - 1][j - 1] + " "); } System.out.println(); } } private static class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public int hashCode() { return ((x << 16) + y); } @Override public boolean equals(Object rhs) { if (rhs == null) { return false; } if (this == rhs) { return true; } Point rhsPoint = (Point) rhs; return ( (this.x == rhsPoint.x) && (this.y == rhsPoint.y) ); } } private static class PointAndCount { Point point; int count; public PointAndCount(Point point, int count) { this.point = point; this.count = count; } @Override public boolean equals(Object rhs) { if (rhs == null) { return false; } if (this == rhs) { return true; } PointAndCount rhsPointAndCount = (PointAndCount) rhs; return ( this.point.equals(rhsPointAndCount.point) && (this.count == rhsPointAndCount.count) ); } } }