n = gets.strip.to_i

# create knights
knights = Array.new()
1.upto(n-1) do |i|
  1.upto(n-1) do |j|
    knights << [i,j]
  end
end

col = 1

# play knights
knights.each do |knight|
  a, b = knight[0], knight[1]

  # create vertices
  graph = Hash.new()
  0.upto(n-1) do |i|
    0.upto(n-1) do |j|
      graph[[i,j]] = Array.new()
    end
  end

  # create edges
  graph.keys.each do |vertex|
    x, y = vertex[0], vertex[1]

    x1, y1 = x+a, y+b
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x+a, y-b
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x-a, y+b
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x-a, y-b
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x+b, y+a
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x+b, y-a
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x-b, y+a
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end

    x1, y1 = x-b, y-a
    if x1 >= 0 && y1 >= 0
      if x1 < n && y1 < n
        if !graph[vertex].include?([x1,y1])
          graph[vertex] << [x1,y1]
        end
      end
    end
  end

  # start bfs
  color = Hash.new()
  distance = Hash.new()
  parent = Hash.new()

  graph.keys.each do |vertex|
    if vertex != [0,0]
      color[vertex] = 1
      distance[vertex] = 4294967296
      parent[vertex] = nil
    end
  end
  color[[0,0]] = 2
  distance[[0,0]] = 0
  parent[[0,0]] = nil
  queue = Array.new()
  queue.push([0,0])
  while !queue.empty?
    u = queue.delete_at(0)
    graph[u].each do |vertex|
      if color[vertex] == 1
        color[vertex] = 2
        distance[vertex] = distance[u] + 1
        parent[vertex] = u
        queue.push(vertex)
      end
    end
    color[u] = 3
  end
  # end bfs

  if col < n
    if distance[[n-1,n-1]] != 4294967296
      print "#{distance[[n-1,n-1]]} "
    else
      print "#{-1} "
    end
    col += 1
  else
    col = 1
    puts
    if distance[[n-1,n-1]] != 4294967296
      print "#{distance[[n-1,n-1]]} "
    else
      print "#{-1} "
    end
    col += 1
  end
end