#!/bin/python3 import sys def print_ans(results): for row in results: for val in row: print(str(val), end=' ') print("") def find_ans(n, a, b): steps = 0 x = 0 if a == b: # there is only one useful move # use it till end is reached while x < n-1: x += a steps += 1 if x != n-1: steps = -1 return steps else: y = 0 # moves ''' x0, y0 = a, b x1, y1 = b, a x2, y2 = a, -b x3, y3 = b, -a x4, y4 = -a, -b x5, y5 = -b, -a x6, y6 = -a, b x7, y7 = -b, a ''' moves = ((a, b), (b, a), (a, -b), (b, -a), (-a, -b), (-b, -a), (-a, b), (-b, a)) present = [] visited = [(0,0)] # first set of moves -- 0 and 1 present.append(moves[0]) present.append(moves[1]) steps = 1 while len(present) != 0: # calculate possible next moves from each position #print("Before") #print(present) for pos in present.copy(): # try all possible next moves from this position for movex in moves: n_pos = tuple(item1 + item2 for item1, item2 in zip(pos, movex)) # check bounds if n_pos[0] < 0 or n_pos[1] < 0 or n_pos[0] >= n or n_pos[1] >= n: pass # check repetiton elif n_pos in present: # drop it and remove pos #present.remove(pos) continue # check whether already visited elif n_pos in visited: # drop it and remove pos #present.remove(pos) continue # check if aim is achieved elif n_pos == (n-1,n-1): return steps+1 else: # update visited visited.append(n_pos) # update present present.append(n_pos) # after trying all moves, remove pos present.remove(pos) steps += 1 #print("After") #print("Steps: {}".format(steps)) #print(present, end="\n\n") # check bounds # check check visited # update present # update visited steps = -1 return steps n = int(input().strip()) #n = 7 results = [] done = [] #find_ans(3, 1, 2) # your code goes here # for each a,b pair for a in range(n-1): results.append([]) for b in range(n-1): # solve the problem and save the answer if (b+1,a+1) in done: results[a].append(results[b][a]) else: results[a].append(find_ans(n, a+1, b+1)) done.append((a+1,b+1)) # print the answers print_ans(results)