import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // your code goes here for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { System.out.print(minMoves(new HashMap(), i, j, 1, n) + " "); } System.out.println(); } //System.out.print(minMoves(new HashMap(), 1, 2, 1, 5) + " "); //System.out.println(minMoves(new ArrayList(), 1, 1, 1, n)); } private static int minMoves(Map moves, int i, int j, int count, int dim) { Map newMoves = new HashMap<>(); if (moves.isEmpty()){ moves.put(new Square(0,0), true); newMoves = knight(moves, new Square(0,0), i, j, dim); } Map tmp = new HashMap(); for (Square s : moves.keySet()) { if (!moves.get(s)){ tmp = knight(moves, s, i, j, dim); for (Square sq : tmp.keySet()) { newMoves.put(sq, false); } moves.put(s, true); } } //System.out.println("OLD Moves: " + moves); //System.out.println("New Moves: " + newMoves); //System.out.println("COUNT: " + count); if (newMoves.keySet().size() == 0) { return -1; } else if (newMoves.get(new Square(dim - 1, dim - 1)) != null){ return count; } else { for (Square s : newMoves.keySet()){ moves.put(s, false); } return minMoves(moves, i, j, count + 1, dim); } } // Return a count of new moves enterd into map private static Map knight(Map prev, Square start, int i, int j, int dim) { Map result = new HashMap<>(); if (start.x - i >= 0 && start.y - j >= 0 && prev.get(new Square(start.x - i, start.y - j)) == null) { result.put(new Square(start.x - i, start.y - j), false); } if (start.x + i < dim && start.y - j >= 0 && prev.get(new Square(start.x + i, start.y - j)) == null) { result.put(new Square(start.x + i, start.y - j), false); } if (start.x + i < dim && start.y + j < dim && prev.get(new Square(start.x + i, start.y + j)) == null) { result.put(new Square(start.x + i, start.y + j), false); } if (start.x - i >= 0 && start.y + j < dim && prev.get(new Square(start.x - i, start.y + j)) == null) { result.put(new Square(start.x - i, start.y + j), false); } //------------ if (start.x - j >= 0 && start.y - i >= 0 && prev.get(new Square(start.x - j, start.y - i)) == null) { result.put(new Square(start.x - j, start.y - i), false); } if (start.x + j < dim && start.y - i >= 0 && prev.get(new Square(start.x + j, start.y - i)) == null) { result.put(new Square(start.x + j, start.y - i), false); } if (start.x + j < dim && start.y + i < dim && prev.get(new Square(start.x + j, start.y + i)) == null) { result.put(new Square(start.x + j, start.y + i), false); } if (start.x - j >= 0 && start.y + i < dim && prev.get(new Square(start.x - j, start.y + i)) == null) { result.put(new Square(start.x - j, start.y + i), false); } return result; } public static class Square{ public int x, y; public Square(int x, int y){ this.x = x; this.y = y; } @Override public boolean equals(Object obj){ Square other = (Square) obj; return this.x == other.x && this.y == other.y; } @Override public int hashCode() { int result = 17; result = 31 * result + x; result = 31 * result + y; return result; } @Override public String toString(){ return "(X: " + x + " Y: " + y + ")"; } } }