忍者のビル登り

忍者のあつしさんは、毎日朝早くから夜遅くまで忍者ビルの屋上から町を警備しています。この忍者ビルは、隣接する 2 つの同じ階数のビルであり、あつしさんは警備のために、ビルとビルの間をジャンプしながら屋上へ向かうことを日課としています。

この 2 つのビルは頻繁に清掃が行われるため、ビル登りの助けとなるはしごや障害となる滑りやすい部分があります。 しかも、はしごや滑りやすい部分の位置は毎日変わります。 そのためあつしさんは、屋上へ向かう方法を毎日考えなければいけません。

あつしさんは二つ並んだ同じ階数のビルの壁を跳び移りながら、ビルの屋上を目指します。ジャンプ はどちらか一方のビルの1階から始められます。向かい側のビルへジャンプするときには、同じ階・1つ上の階・2 つ上の階の、いずれかに飛び移ることができます。

壁には以下の 3 種類があり、それぞれの壁にジャンプした後の移動が決まっています。

• 0. 普通の壁: 上下の移動はしない。次のジャンプはそこから行う。
• 1. はしご: はしごは 2 つ以上の階にまたがってかかっており、今いるはしごの一番上まで移動する。次のジャンプはそこから行う。
• 2. すべる壁: 普通の壁かはしごの一番上まで滑り落ちる。次のジャンプはそこから行う。

また、壁は 1 階から屋上のすぐ下の最上階まであり、屋上へはそのビルの最上階からのみ行くことが できます。また、ビルの最下階の壁はすべる壁にはなりません。

2 つのビルの階数 n と 2 つのビルの壁の種類を入力とし、最少で何回目のジャンプで最上階までたどり着き、屋上まで行くことができるかを出力するプログラムを作成してください。なお、どちらのビルの屋上にたどり着いてもよいものとします。ただし、あつしさんがどちらのビルの屋上へもたどり着けない場合は“NA”と出力してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

n
a1 a2 ... an
b1 b2 ... bn

１行目にビルの階数 n (3 ≤ n ≤ 100) が与えられます。２行目に１ つ目のビルの 1 階から n 階までの壁の情報 a_i、３行目に２つ目のビルの 1 階から n 階までの壁の情報 b_i が与えられます。a_i, b_i はi 階目の壁の情報を表し、0 が普通の壁、1 がはしご(i 階と i+1 階にまたがる)、2 がすべる壁を表します。

データセットの数は 60 を超えません。

Output

入力データセットごとに、ジャンプの回数を１行に出力します。

Sample Input

8
0 0 0 2 2 2 0 0
1 1 1 1 0 0 0 0
4
1 1 2 2
0 0 2 2
0

Output for the Sample Input

4
NA