import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int getMinMoves(int n, int a, int b){ final int MY_MAX = n*n; int[][] dist = new int[n][n]; boolean[][] visited = new boolean[n][n]; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ dist[i][j] = MY_MAX; // like inf for the given constraints visited[i][j] = false; } } int numVisited = 0; boolean firstIteration = true; // currently selected node int cx = 0; int cy = 0; // always start from here dist[0][0] = 0; // possible deltas int[] dx = new int[]{+a,+a,-a,-a,+b,+b,-b,-b}; int[] dy = new int[]{+b,-b,+b,-b,+a,-a,+a,-a}; // distance for each delta is one move int dd = 1; while(numVisited<n*n){ // find the node with the minimum distance int minDist = MY_MAX; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(visited[i][j]==false && dist[i][j]<=minDist){ minDist = dist[i][j]; cx = i; cy = j; } } } // mark current node as visited visited[cx][cy] = true; numVisited++; // System.out.println("c"+cx+","+cy); // look at the neighbors of the current node boolean cHasUnvisitedNeighbor = false; // check all neighbors for(int i=0; i<dx.length; i++){ int nx = cx+dx[i]; int ny = cy+dy[i]; // check if the neighbor is on the board boolean nOnBoard = nx>=0 && nx<n && ny>=0 && ny<n; // if it has not been visited compute the distance if(nOnBoard && visited[nx][ny]==false){ cHasUnvisitedNeighbor = true; int alt = dist[cx][cy] + dd; if(alt < dist[nx][ny]){ dist[nx][ny] = alt; } } } // if the current node does not have a single neighbor then we're screwed // if(cHasUnvisitedNeighbor==false){ // break; // } } if(dist[n-1][n-1]==MY_MAX){ return -1; } else{ return dist[n-1][n-1]; } } 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++){ int minMoves = getMinMoves(n,i,j); System.out.print(minMoves+" "); } System.out.println(); } } }