import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private static int sMax; private static int[][] moveBoard; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // your code goes here sMax = n * n + 1; for(int a = 1; a < n; a++) { String[] moves = new String[n - 1]; for(int b = 1; b < n; b++) { moves[b - 1] = calculateMoves(a, b, n) + ""; } System.out.println(String.join(" ", moves)); } } private static int calculateMoves(int a, int b, int n) { moveBoard = new int[n][n]; for(int x = 0; x < moveBoard.length; x++) { for(int y = 0; y < moveBoard.length; y++) { moveBoard[x][y] = sMax; } } moveBoard[0][0] = 0; int result = calculateMoves(0, 0, a, b, new boolean[n][n]); if(result == sMax) { return -1; } else { return result; } } private static int calculateMoves(int x, int y, int a, int b, boolean[][] board) { int n = board.length; board[x][y] = true; if(x == n - 1 && y == n - 1) { return 0; } int bestSoFar = sMax; int[][] nextMoves = getNextMoves(x, y, a, b); for(int i = 0; i < nextMoves.length; i++) { int nextX = nextMoves[i][0]; int nextY = nextMoves[i][1]; if(0 <= nextX && nextX < n && 0 <= nextY && nextY < n && !board[nextX][nextY] && moveBoard[x][y] + 1 < moveBoard[nextX][nextY] ) { boolean[][] newBoard = board.clone(); for(int j = 0; j < board.length; j++) { newBoard[j] = board[j].clone(); } moveBoard[nextX][nextY] = moveBoard[x][y] + 1; int moves = calculateMoves(nextX, nextY, a, b, newBoard); if(moves != sMax) { bestSoFar = Math.min(bestSoFar, 1 + moves); } } } return bestSoFar; } private static int[][] getNextMoves(int x, int y, int a, int b) { return new int[][] { {x + a, y + b}, {x + a, y - b}, {x - a, y + b}, {x - a, y - b}, {x + b, y + a}, {x + b, y - a}, {x - b, y + a}, {x - b, y - a} }; } }