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

while (nxt = stack.shift)
  next if result1[nxt] >= 10
  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 = nxt[next_index]) == "f" or c == "0"
      next_field = nxt.dup
      next_field[idx] = c
      next_field[next_index] = "0"
      next if result1[next_field]
      result1[next_field] = result1[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") }
  
  if (ans = result1[start = pat.join])
    puts ans
    next
  end
  
  result2 = {}
  result2[start] = 0
  stack = [start]
  str = "NA"
  f = true
  
  while (nxt = stack.shift) and f
    next if result2[nxt] >= 10
    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 = nxt[next_index]) == "f" or c == "0"
        next_field = nxt.dup
        next_field[idx] = c
        next_field[next_index] = "0"
        next if result2[next_field]
        if result1[next_field]
          str = (result1[next_field] + result2[nxt] + 1).to_s
          return false
        end
        result2[next_field] = result2[nxt] + 1
        stack << next_field
      end
      true
    }
    f = doit.(nxt.index("0"))
    doit.(nxt.rindex("0")) if f
  end
  puts str
end
