def knightlOnAChessboard(n):
    
    def get_moves(position:tuple, a:int, b:int, cost:int):
        x, y = position 
        moves_x = {"a":[],"b":[]}
        moves_y = {"a":[],"b":[]} 
        
        for coordinate, moves in zip([x,y], [moves_x,moves_y]):
          for delta, final_moves in zip([a,b], [moves["a"], moves["b"]]):
            if (coordinate+delta <= n-1):
                final_moves.append(coordinate+delta) 
            if (coordinate-delta >= 0): 
                final_moves.append(coordinate-delta)
        
        moves_a_b = [(x,y, cost + 1) for x in moves_x["a"] for y in moves_y["b"]]
        moves_b_a = [(x,y, cost + 1) for x in moves_x["b"] for y in moves_y["a"]]
        
        return moves_a_b + moves_b_a

    def ucs(queue:list, visited:list, a:int, b:int):
        while (len(queue)):
          x,y, cost = queue.pop(0)
          if (x,y) == (n-1, n-1):
            return cost
          if (x,y) not in visited:
            visited.append((x,y))
            moves = get_moves((x,y),a,b, cost)
            queue.extend(moves)
        return -1
            
    results=[]
    for i in range(1,n):
        list_results=[]
        for j in range(1,n):
            cost = ucs([(0,0,0)], [], i,j)
            list_results.append(cost)
        results.append(list_results)
        
    return results