Maze

Προκειμένου να βγάλετε μερικά δολάρια, αποφασίσατε να συμμετάσχετε σε ένα επιστημονικό πείραμα. Σας ταΐζουν με πολλή πίτσα, μετά με περισσότερη πίτσα και μετά σας ζητούν να βρείτε το δρόμο σας μέσα στην πόλη με ένα σκούτερ που κινείται μόνο με ενέργεια πίτσας. Φυσικά, η πόλη έχει πολλές διασταυρώσεις και αυτές οι διασταυρώσεις είναι αυστηρά ελεγχόμενες. Σε κάποιες διασταυρώσεις απαγορεύεται να μπείτε, σε κάποιες μπορείτε να κινηθείτε μόνο βόρεια/νότια καθώς εξέρχεστε από τη διασταύρωση- σε άλλες σας επιτρέπουν να κιθείτε μόνο ανατολικά/δυτικά καθώς εξέρχεστε από τη διασταύρωση- και στις υπόλοιπες σας επιτρέπουν να πηγαίνετε προς οποιαδήποτε κατεύθυνση της πυξίδας (βόρεια, νότια, ανατολικά ή δυτικά).

Ευτυχώς, οι φίλοι σας οι επιστήμονες που διεξάγουν το πείραμα, σας έχουν δώσει έναν χάρτη της πόλης (σχεδιασμένο στο πίσω μέρος ενός κουτιού πίτσας), με μια διάταξη συμβόλων που υποδεικνύει τον τρόπο με τον οποίο μπορείτε να κινηθείτε μέσα στην πόλη. Συγκεκριμένα, υπάρχουν υπάρχουν ~4~ διαφορετικά σύμβολα στο κουτί:

• Το σύμβολο ~+~ υποδεικνύει ότι μπορούμε να κινηθούμε προς οποιαδήποτε κατεύθυνση (βόρεια/νότια/ανατολικά/δυτικά) από τη θέση που βρισκόμαστε.
• Το σύμβολο ~-~ υποδεικνύει ότι μπορούμε να κινηθούμε μόνο ανατολικά ή δυτικά από αυτή τη θέση.
• Το σύμβολο ~|~ υποδεικνύει ότι μπορούμε να κινηθούμε μόνο βόρεια ή νότια από αυτή τη θέση.
• Το σύμβολο ~*~ υποδεικνύει ότι δεν μπορούμε να καταλάβουμε αυτή τη θέση.

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

Είσοδος

Η είσοδος ξεκινά με τον αριθμό ~t\;(1 \le t \le 10)~ σε ξεχωριστή γραμμή, ο οποίος υποδεικνύει πόσα διαφορετικά αρχεία ελέγχου περιέχονται σε αυτό το φάκελο. Κάθε αρχείο ελέγχου αρχίζει µε έναν αριθµό ~r~ σε µια γραµµή, ακολουθούµενο από έναν αριθµό ~c~ στην επόµενη γραµµή ~(1 \le r,\; c \le 20)~. Οι επόµενες ~r~ γραµµές περιέχουν ~c~ το πλήθος χαρακτήρες, όπου κάθε χαρακτήρας είναι ένας από τους ακόλουθους: { ~+, *, -, |~ }. Μπορείτε να υποθέσετε ότι η βορειοδυτική γωνία της πόλης είναι μια θέση που μπορεί να καταληφθεί (δηλαδή, δεν θα σημειωθεί με ~*~).

Έξοδος

Η έξοδος θα έχει μήκος ~t~ γραμμών, με έναν ακέραιο ανά γραμμή. Ο ακέραιος αριθμός στη γραμμή ~i\;(1 \le i \le t)~ υποδηλώνει τον ελάχιστο αριθμό διασταυρώσεων από τις οποίες απαιτείται να περάσετε καθώς κινείστε από τη βορειοδυτική γωνία της πόλης προς τη νοτιοανατολική γωνία της. Εάν δεν υπάρχει τρόπος να μεταβείτε από τη βορειοδυτική στη νοτιοανατολική γωνία, εξάγετε ~-1~ για το συγκεκριμένο αρχείο ελέγχου.

Παράδειγμα

input

3
2
2
-|
*+
3
5
+||*+
+++|+
**--+
2
3
+*+
+*+

output

3
7
-1