The path in the colored field

Το τετράγωνο πεδίο αποτελείται από ~M \times M~ κελιά. Κάθε κελί είναι χρωματισμένο με ένα από τα τρία χρώματα (~1~, ~2~, ~3~). Η αρχική κατάσταση επιλέγεται σε ένα από τα κελιά χρώματος ~1~. Σε κάθε βήμα επιτρέπεται η μετακίνηση ενός κελιού πάνω, κάτω, αριστερά ή δεξιά παραμένοντας εντός του πεδίου.

Πρέπει να προσδιορίσετε τον ελάχιστο αριθμό βημάτων που απαιτείται να κάνει κάποιος για να πάρει ένα κελί χρώματος ~3~ ανεξάρτητα από την αρχική κατάσταση.

Σημειώστε ότι το πεδίο περιέχει τουλάχιστον ένα κελί χρώματος ~1~ και τουλάχιστον ένα κελί χρώματος ~3~.

Είσοδος

Η είσοδος αποτελείται από αρκετά μπλοκς εισόδου.

Η πρώτη γραµµή κάθε µπλοκ περιέχει τον ακέραιο ~M~, το µέγεθος του πεδίου.

Στη συνέχεια ακολουθούν ~M~ γραμμές με τα χρώματα των κελιών.

Έξοδος

Για κάθε μπλοκ εισόδου η έξοδος θα πρέπει να αποτελείται από μία γραμμή με έναν ακέραιο αριθμό, τον ελάχιστο αριθμό βημάτων που πρέπει να κάνει κάποιος για να πάρει ένα κελί χρώματος ~3~ ανεξάρτητα από την αρχική κατάσταση.

Παράδειγμα

input

4
1223
2123
2213
3212
2
12
33

output

3
1