def f h,n,m
h[n]=0
q=[n]
(yield a=q.shift
p "#{a} #{h[a]}"
[a.index(0),a.rindex(0)].map{|j|[6,-6,1,-1].map{|i|a[k=i+j]>0&&(b=a.dup
b[j],b[k]=b[k],b[j]
h[b]||=(q<<b;h[a]+1))}})while q[0]&&h[q[0]]<m
end
o=[-1]
d=o*2
f(g={},d+[0]+o*4+[*1..3]+d+[*4..8]+d+[*9..11]+o*4+[0]+o*6,12){}
puts f(h={},d+[$_.to_i]+o*3+[1,0,1,2].flat_map{|i|o*i+gets.split.map(&:to_i)+o*i+o}+o*3,10){|a|g[a]&&(break h[a]+g[a])}||:NA while gets>?0