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(); Position start = new Position(0, 0); Position destination = new Position(n-1, n-1); List previousMoves = new ArrayList(); for(int i = 1; i < n; i++) { for(int j = 1; j < n; j++) { int findMinimalPath = findMinimalPath(start, destination, previousMoves, 0, i, j, n); if(findMinimalPath == Integer.MAX_VALUE) { findMinimalPath = -1; } System.out.print(findMinimalPath + " "); previousMoves.clear(); } System.out.println(); } in.close(); } private static int findMinimalPath(Position current, Position destination, List previousMoves, int count, int a, int b, int n) { int minimalSteps = Integer.MAX_VALUE; Set possibleMoves = getPossibleMoves(current, previousMoves, a, b, n); for (Position position : possibleMoves) { if(position.equals(destination)) { return count + 1; } else { previousMoves.add(current); count++; int moveCount = findMinimalPath(position, destination, previousMoves, count, a, b, n); previousMoves.remove(current); count--; if( moveCount < minimalSteps) { minimalSteps = moveCount; } } } return minimalSteps; } private static Set getPossibleMoves(Position current, List previousMoves, int a, int b, int n) { Set positionList = new HashSet(); Position p1 = new Position(current.x + a, current.y + b); Position p2 = new Position(current.x + a, current.y - b); Position p3 = new Position(current.x - a, current.y + b); Position p4 = new Position(current.x - a, current.y - b); Position p5 = new Position(current.x + b, current.y + a); Position p6 = new Position(current.x + b, current.y - a); Position p7 = new Position(current.x - b, current.y + a); Position p8 = new Position(current.x - b, current.y - a); positionList.add(p1); positionList.add(p2); positionList.add(p3); positionList.add(p4); positionList.add(p5); positionList.add(p6); positionList.add(p7); positionList.add(p8); positionList.removeAll(previousMoves); positionList.remove(current); Iterator iterator = positionList.iterator(); while(iterator.hasNext()) { Position next = iterator.next(); if(next.x < 0 || next.y < 0 || next.x > (n-1) || next.y > (n-1)) { iterator.remove(); } } return positionList; } } class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object obj) { Position other = (Position)obj; return x == other.x && y == other.y; } @Override public int hashCode() { return 19 * Integer.hashCode(x) * Integer.hashCode(y); } @Override public String toString() { return x + "," + y; } }