#!/bin/python3 import sys from queue import Queue def in_range(i,j): return 0 <= i < n and 0 <= j < n n = int(input().strip()) # your code goes here ans = [[-1 for i in range(n-1)] for j in range(n-1)] for i in range(1,n): for j in range(1,n): board = [[-1 for i in range(n)] for j in range(n)] board[0][0] = 0 q = Queue() visited = set() q.put((0,0)) visited.add((0,0)) while not q.empty(): x,y = q.get() step = board[x][y] if (x,y) == (n-1,n-1): ans[i-1][j-1] = board[n-1][n-1] break set_of_moves = [(x+c1*i,y+c2*j) for c1 in[-1,1] for c2 in [-1,1]] + [(x+c1*j,y+c2*i) for c1 in[-1,1] for c2 in [-1,1]] for pt in set_of_moves: if in_range(*pt) and pt not in visited: board[pt[0]][pt[1]] = step + 1 visited.add(pt) q.put(pt) for ar in ans: print(*ar)