start = "fff0fff" "ff123ff" "f45678f" "ff9abff" "fff0fff"
result = {}
result[start] = 0
stack = [start]

while (nxt = stack.shift)
  doit = ->(idx) {
    [1, -1, 7, -7].each do |di|
      next_index = idx + di
      next if next_index < 0 or next_index >= 35
      next if (c = start[next_index]) == "f" or c == "0"
      next_field = nxt.dup
      next_field[idx] = c
      next_field[next_index] = "0"
      next if result[next_field]
      result[next_field] = result[nxt] + 1
      stack << next_field
    end
  }
  doit.(nxt.index("0"))
  doit.(nxt.rindex("0"))
end

pat = Array.new(5)
until (pat[0] = gets.to_i) == -1
  pat[0] = pat[0].to_s(16).center(7, "f")
  4.times {|i| pat[i + 1] = gets.split.map {|a| a.to_i.to_s(16)}.join.center(7, "f") }
  num = result[pat.join]
  puts num ? num : "NA"
end
