while 0<n=gets.to_i
h={}
q=[[1,0,0],[0]*3]
a=q.map{gets.split.map &:to_i}
h[(b,f,c=q.shift)[0,2]]||=(
u,v=a[b][f,2]
u&&(u>1||u>0&&v==1?(q=[[b,u>1?f-1:f+1,c]]+q):f>n-2?(break):3.times{|i|q<<[1-b,f+i,c+1]})
c)while t=q[0]
puts t ?c:"NA"
end