import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Node { int x; int y; Node(int x, int y) { this.x = x; this.y = y; } } public class Solution { static HashMap<String,Integer> memo = new HashMap<String,Integer>(); static int arraySize; static int KnightL(int a,int b,int n) { String key = b+"-"+a; if(memo.containsKey(key)) { return memo.get(key); } int[][] distances = new int[n][n]; LinkedList<Node> queue = new LinkedList<Node>(); queue.add(new Node(0,0)); while(!queue.isEmpty()) { Node currentNode = queue.pop(); if(currentNode.x == n-1 && currentNode.y == n-1) { key=a+"-"+b; int distValue = distances[currentNode.x][currentNode.y]; memo.put(key,distValue); return distValue; } ArrayList<Node> possibleMoves = getAdjacentNodes(currentNode,a,b,distances); for(Node node:possibleMoves) { distances[node.x][node.y] = distances[currentNode.x][currentNode.y] + 1; queue.add(node); } } return -1; } static ArrayList<Node> getAdjacentNodes(Node node,int a,int b,int[][] distances) { int x = node.x; int y = node.y; ArrayList<Node> nodes = new ArrayList<Node>(); if(islegal(x-a,y-b)&& distances[x-a][y-b] == 0) { nodes.add(new Node(x-a,y-b)); } if(islegal(x-b,y-a) && distances[x-b][y-a] == 0) { nodes.add(new Node(x-b,y-a)); } if(islegal(x+a,y+b) && distances[x+a][y+b] == 0) { nodes.add(new Node(x+a,y+b)); } if(islegal(x+b,y+a) && distances[x+b][y+a] == 0) { nodes.add(new Node(x+b,y+a)); } if(islegal(x-a,y+b) && distances[x-a][y+b] == 0) { nodes.add(new Node(x-a,y+b)); } if(islegal(x+a,y-b) && distances[x+a][y-b] == 0) { nodes.add(new Node(x+a,y-b)); } if(islegal(x+b,y-a) && distances[x+b][y-a] == 0) { nodes.add(new Node(x+b,y-a)); } if(islegal(x-b,y+a) && distances[x-b][y+a] == 0) { nodes.add(new Node(x-b,y+a)); } return nodes; } static void findPossiblePathsFromStoT(int n) { for(int a=1;a<n;a++) { for(int b=1;b<n;b++) { System.out.print(KnightL(a,b,n)+" "); } System.out.println(); } } static boolean islegal(int x, int y) { if(x>=0 && x<arraySize && y>=0 && y<arraySize) { return true; } return false; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); arraySize = n; findPossiblePathsFromStoT(n); // your code goes here } }