Ως γνωστό η Αριάδνη είναι αυθεντία στους λαβυρίνθους. Ο Παντελής τον τελευταίο καιρό έχει ξεκινήσει μαθήματα αρχιτεκτονικής με εξειδίκευση την κατασκευή λαβυρίνθων. Για το λόγο αυτό αποτάθηκε στην Αριάδνη για βοήθεια. Θέλει να βεβαιωθεί ότι οι λαβύρινθοι που φτιάχνει είναι σωστοί. Ένας λαβύρινθος είναι σωστός αν:

• Έχει μόνο μια είσοδο και μόνο μία έξοδο
• Υπάρχει τουλάχιστον μια διαδρομή από την είσοδο στην έξοδο

Επιπλέον ο Παντελής θέλει να τοποθετήσει τον Μινώταυρο μέσα στον λαβύρινθο σε τέτοιο σημείο που να είναι ακίνδυνος για όσους είναι μέσα στον λαβύρινθο.

Δεδομένα Εισόδου

• Στην 1η γραμμή έχουμε έναν ακέραιο αριθμό T (0<Τ<=100) που αντιστοιχεί στον αριθμό των test cases. Για κάθε ένα από τα τεστ:
• Στην 1η γραμμή δίνονται δύο ακέραιοι αριθμοί Ν και Μ (0<Ν,Μ<=20) που αντιστοιχούν στο μέγεθος του λαβυρίνθου
• Ακολουθεί ο λαβύρινθος όπου ο χαρακτήρας ‘#’ αντιστοιχεί σε τοίχο, ο χαρακτήρας ‘.’ σε πέρασμα και ο χαρακτήρας ‘*’ στον Μινώταυρο.

Δεδομένα Εξόδου

Για κάθε ένα από τα τεστ το πρόγραμμα θα τυπώνει ένα από τα παρακάτω μηνύματα:

• invalid αν ο λαβύρινθος δεν είναι σωστός.
• valid no danger αν λαβύρινθος είναι σωστός και δεν υπάρχει κίνδυνος από τον Μινώταυρο.
• valid danger αν λαβύρινθος είναι σωστός και υπάρχει κίνδυνος από τον Μινώταυρο.