Bessie a Camelot ha un problema: attraversare foresta dei Knights of Ni. Chiedono un solo arbusto per passare sicura. Il tempo conta, deve trovarlo e portarlo più presto possibile.

Mappa quadrata usuale parallela agli assi $X$, $Y$, dimensioni $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Segna inizio, unica casella cavalieri, tutti arbusti e aree percorribili. Paludi, scogliere e conigli assassini bloccano alcune. Senza arbusto non passa la casella cavalieri.

Per seguire bene mappa solo nord, est, sud, ovest, non diagonali. Una casella vicina richiede un giorno.

Ottenere e consegnare è garantito. Trova modo più rapido.

Input

Riga $1$: interi $W$, $H$ con spazio.

Righe $2..?$: mappa per righe, prima nordovest, ultima sudest, interi da ovest a est. Nuova riga mappa inizia nuova riga input, massimo 40 interi separati da spazi. Se $W \le 40$, una riga copre tutta riga mappa; se $W > 40$, più righe, 40 interi ciascuna salvo forse ultima. Riga input non copre mai più righe mappa.

Valori:

• 0: percorribile.
• 1: invalicabile.
• 2: inizio Bessie.
• 3: Knights of Ni.
• 4: arbusto.

Output

Riga $1$: $D$, minimo giorni per ottenere e consegnare.

Esempi

Input 1

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

Output 1

11

Spiegazione

Larghezza $8$, altezza $4$, parte terza riga vicino cavalieri.

Può fare N, W, N, S, E, E, N, E, E, S, S: arbusto nordovest, aggira barriere a est poi sud ai cavalieri.