import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.awt.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Map mapi = new HashMap(); for(int i = 1; i < n;i++) { StringJoiner strBuilder = new StringJoiner(" "); for(int j=1; j < n;j++) { String key = String.valueOf(j) + "," + String.valueOf(i); Integer value = mapi.get(key); if (value == null) { SolutionCalculator c = new SolutionCalculator(i, j, n); value = c.calcShortestPath(); if (value == Integer.MAX_VALUE) { value = -1; } mapi.put(String.valueOf(j) + "," + String.valueOf(i), value); } strBuilder.add(String.valueOf(value)); } System.out.println(strBuilder.toString()); } } } class SolutionCalculator { private int i; private int j; private int n; private HashSet visited = new HashSet(); Queue execQueue = new LinkedList(); public SolutionCalculator(int i, int j, int n) { this.i = i; this.j = j; this.n = n; } public int calcShortestPath() { this.markAsVisited(0, 0); SolutionState state = new SolutionState(0, 0, 0); this.execQueue.add(state); return this.recursiveCalcShortestPath(); } public int recursiveCalcShortestPath() { SolutionState state = this.execQueue.poll(); if (state == null) return -1; if (state.x == n-1 && state.y== n-1) return state.score; ArrayList arr = this.getNeighbors(state); for(SolutionState s : arr) { this.execQueue.add(s); } return recursiveCalcShortestPath(); } private void addPoint(SolutionState state, int x, int y, ArrayList acc) { if (x < this.n && x >= 0 && y < this.n && y >= 0 && !this.isVisited(x, y)) { this.markAsVisited(x, y); SolutionState newState = new SolutionState(x, y, state.score + 1); acc.add(newState); } } private ArrayList getNeighbors(SolutionState state) { ArrayList neighbors = new ArrayList(); this.addPoint(state, state.x + this.i, state.y + this.j, neighbors); this.addPoint(state, state.x + this.j, state.y + this.i, neighbors); this.addPoint(state, state.x - this.i, state.y + this.j, neighbors); this.addPoint(state, state.x - this.j, state.y + this.i, neighbors); this.addPoint(state, state.x + this.i, state.y - this.j, neighbors); this.addPoint(state, state.x + this.j, state.y - this.i, neighbors); this.addPoint(state, state.x - this.i, state.y - this.j, neighbors); this.addPoint(state, state.x - this.j, state.y - this.i, neighbors); return neighbors; } private void markAsVisited(int x, int y) { this.visited.add(String.valueOf(x) + "," + String.valueOf(y)); } private boolean isVisited(int x, int y) { return this.visited.contains(String.valueOf(x) + "," + String.valueOf(y)); } } class SolutionState { public int score; int x; int y; public SolutionState(int x, int y, int score) { this.score = score; this.x = x; this.y = y; } }