Mountain Passage

Ο Alp ο ορειβάτης βρίσκεται στη βορειοδυτική γωνία μιας τετράγωνης περιοχής ορεινού εδάφους και επιθυμεί να βρει ένα πέρασμα στην απέναντι (νοτιοανατολική) γωνία. Ο Alp βρίσκεται επί του παρόντος σε ένα υψόμετρο στο οποίο δεν χρειάζεται οξυγόνο, αλλά σε οποιοδήποτε υψηλότερο υψόμετρο απαιτείται οξυγόνο. Το οξυγόνο, όταν απαιτείται, χρησιμοποιείται με ρυθμό μίας μονάδας ανά οριζόντιο βήμα.

Η βορειοδυτική γωνία του εδάφους βρίσκεται στη θέση ~(1, 1)~ και η νοτιοανατολική γωνία βρίσκεται στη θέση ~(n, n)~, όπου ~n~ είναι ένας θετικός ακέραιος που διαβάζεται από το αρχείο εισόδου. Το υψόμετρο κάθε σημείου ~(x, y)~, ~(1 \le x, y \le n)~, είναι ένας ακέραιος που διαβάζεται από την είσοδο. Κάθε υψόμετρο καταλαμβάνει μία μόνο γραμμή στο αρχείο εισόδου.

Ο Alp κινείται σε μια σειρά από οριζόντια βήματα, όπου κάθε βήμα μετακινεί το Alp μια μονάδα βόρεια, μια μονάδα νότια, μια μονάδα ανατολικά ή μια μονάδα δυτικά. Ο Alp πρέπει να παραμείνει στην τετράγωνη περιοχή και δεν μπορεί να ανέβει ή να κατέβει πάνω από 2 μονάδες υψομέτρου σε ένα μόνο βήμα. Εάν το υψόμετρο είτε στην αρχή είτε στο τέλος του βήματος απαιτεί οξυγόνο, μια μονάδα οξυγόνου καταναλώνεται από την Alp κατά τη διάρκεια του βήματος.

Η πρώτη γραμμή εισόδου είναι ένας θετικός ακέραιος αριθμός που υποδεικνύει τον αριθμό των διαδρομών που πρέπει να κάνει ο Alp. Για κάθε διαδρομή υπάρχει ένας αριθμός γραμμών εισόδου. Η πρώτη γραμμή για κάθε διαδρομή περιέχει έναν ακέραιο αριθμό ~n \le 25~, που υποδεικνύει το μέγεθος της τετραγωνικής επιφάνειας του εδάφους. Οι επόμενες ~n^2~ γραμμές περιέχουν η καθεμία από έναν ακέραιο αριθμό που υποδεικνύει το υψόμετρο ενός συγκεκριμένου σημείου εδάφους. Τα υψόμετρα δίνονται για τα σημεία με την ακόλουθη σειρά:

~(1, 1),\;(1, 2),\;(1, 3) \cdots (1, n),\;(2, 1), \;2, 2),\; \cdots (n, 1),\;(n, 2),\;\cdots (n, n)~

Για κάθε διαδρομή, εάν υπάρχει ένα πέρασμα, η έξοδος είναι μια ενιαία γραμμή που περιέχει έναν ακέραιο αριθμό που δείχνει τον αριθμό των μονάδων οξυγόνου που καταναλώθηκε. Εάν δεν υπάρχει πέρασμα, η έξοδος είναι μια γραμμή που περιέχει το μήνυμα "CANNOT MAKE THE TRIP". Οι γραμμές εξόδου για τα ταξίδια θα πρέπει να διαχωρίζονται από μία κενή γραμμή.

Παράδειγμα

input

2
5
5
4
3
2
1
7
5
6
6
6
8
8
8
9
6
9
6
9
9
6
4
5
4
5
3
2
4
9
9
4

output

5
CANNOT MAKE THE TRIP