Πρόβλημα

Φαντάζομαι το πρόβλημα των ~N~ Βασιλισσών είναι γνωστό σε όποιον έχει διαβάσει πρόβλημα το οποίο λύνεται με παλινδρόμηση (backtracking). Σε αυτό το πρόβλημα, πρέπει να μετρήσετε τους τρόπους για να τοποθετήσουμε ~N~ βασίλισσες σε ~N\times N~ σκακιέρα ώστε καμία να μην απειλείται. Για να δυσκολέψουμε (ή απλοποιήσουμε) το πρόβλημα, προσθέτουμε μερικά κακά κελιά όπου οι βασίλισσες δεν μπορούν να τοποθετηθούν. Λάβετε υπόψη σας ότι τα κακά τετράγωνα δεν μπορούν να χρησιμοποιηθούν για να εμποδίσουν την επίθεση των βασιλισσών.

Συμμετρικές λύσεις θεωρούνται διαφορετικές

Μορφή εισόδου

Η είσοδος αποτελείται το πολύ από 10 περιπτώσεις δοκιμών. Κάθε περίπτωση περιέχει έναν ακέραιο αριθμό ~N~ (3 ≤ ~N~ ≤ 15) στην πρώτη γραμμή. Οι επόμενες ~N~ γραμμές αντιπροσωπεύουν τον πίνακα, όπου τα κενά τετράγωνα αναπαρίστανται με τελείες . , τα κακά τετράγωνα αναπαρίστανται με αστερίσκους *. Η τελευταία περίπτωση ακολουθείται από ένα απλό μηδέν, το οποίο δεν πρέπει να επεξεργαστεί.

Μορφή εξόδου

Για κάθε περίπτωση, εκτυπώστε τον αριθμό της και το πλήθος των λύσεων, όπως στο παρακάτω παράδειγμα.

Παράδειγμα

Είσοδος:

8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
0

Έξοδος:

Case 1: 92
Case 2: 1