#!/bin/python3 import sys from collections import deque def main(n): for a in range(1, n): row = [] for b in range(1, n): row.append(move_knight([a, b], n)) print(' '.join(str(x) for x in row)) def move_knight(movement, n): visited = [[0, 0]] positions = deque() positions.append([[0, 0], 0]) moves = 0 while positions: current = positions.popleft() c_position = current[0] c_move = current[1] future = future_positions(movement, current[0], n) for f in future: if f == [n - 1, n - 1]: return c_move + 1 elif f in visited: pass else: positions.append([f, c_move + 1]) visited.append(f) return -1 def future_positions(movement, current, n): f_ps = [] x = current[0] y = current[1] a = movement[0] b = movement[1] for f_x in [x - a, x + a]: if valid(f_x, n): for f_y in [y - b, y + b]: if valid(f_y, n): f_ps.append([f_x, f_y]) for f_x in [x - b, x + b]: if valid(f_x, n): for f_y in [y - a, y + a]: if valid(f_y, n): f_ps.append([f_x, f_y]) return f_ps def valid(i, n): return i >= 0 and i < n n = int(input().strip()) main(n)