### constant

MAX_INT = (1 << 30)

### main

while true
  n = gets.strip.to_i
  break if n == 0

  bldgs = 2.times.map{[]}

  bldgs[0] = gets.strip.split(' ').map{|s| s.to_i}
  bldgs[1] = gets.strip.split(' ').map{|s| s.to_i}
  #p bldgs

  min_j = MAX_INT

  for bs in [0, 1]
    dists = 2.times.map{n.times.map{MAX_INT}}
    visit = 2.times.map{n.times.map{false}}

    fs = 0
    while fs < n - 1 && bldgs[bs][fs] == 1 && bldgs[bs][fs + 1] == 1
      fs += 1
    end

    q = [[bs, fs]]
    dists[bs][fs] = 0
    visit[bs][fs] = true

    while ! q.empty?
      b0, f0 = q.shift
      next if f0 >= n - 1

      b1 = 1 - b0
      for f2 in (f0..(f0 + 2)).select{|f| f < n}
        f1 = f2

        case bldgs[b1][f1]
        when 1
          while f1 < n - 1 && bldgs[b1][f1 + 1] == 1
            f1 += 1
          end
        when 2
          while f1 > 0 && bldgs[b1][f1] == 2
            f1 -= 1
          end
        end

        if ! visit[b1][f1]
          dists[b1][f1] = dists[b0][f0] + 1
          visit[b1][f1] = true
          q << [b1, f1]
        end
      end
    end

    min_d = (0..1).map{|i| dists[i][n - 1]}.min
    min_j = min_d if min_j > min_d
  end

  puts (min_j >= MAX_INT ? 'NA' : min_j)
end