Down Went The Titanic

Μετά τη σύγκρουσή του με το παγόβουνο, ο Τιτανικός βυθίστηκε. Τώρα, άνθρωποι πλέουν στα κρύα νερά, παλεύοντας με τον θάνατο. Διασωστικά πλοία θα φτάσουν στο σημείο για να τους σώσουν. Αλλά μέχρι να φτάσουν τα πλοία, θα πρέπει να καταφέρουν να επιβιώσουν. Σκεφτείτε μια περιοχή με νερό, άνθρωπους, πάγο που επιπλέει, μεγάλα κομμάτια ξύλου κ.λπ. Λάβετε τώρα υπόψιν σας τα παρακάτω σύμβολα:

~*~ Άνθρωποι που βρίσκονται πάνω σε πάγο που επιπλέει. Οι άνθρωποι αυτοί θέλουν να μετακινηθούν από εδώ, καθώς τα κομμάτια του πάγου δεν μπορούν να τους στηρίξουν για μεγάλο χρονικό διάστημα. Μόλις ένας άνθρωπος μετακινηθεί από εδώ, το κομμάτι αυτό του πάγου θα βυθιστεί. Οι άνθρωποι μπορούν να κινηθούν προς οποιαδήποτε από τις τέσσερις κατευθύνσεις (βόρεια, ανατολικά, δυτικά και νότια).

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

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

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

# Μεγάλο κομμάτι ξύλου. Αυτός ο τόπος είναι ασφαλής. Οι άνθρωποι μπορούν να μετακινηθούν και να παραμείνουν εδώ μέχρι να φτάσουν τα διασωστικά πλοία. Ένα μεγάλο κομμάτι ξύλο θα βυθιστεί εάν παραμείνουν περισσότεροι από ~P~ άνθρωποι πάνω σε αυτό ταυτόχρονα. Δεδομένης της περιγραφής της περιοχής, θα πρέπει να βρείτε μια βέλτιστη στρατηγική που να διασφαλίζει τον μέγιστο αριθμό επιζώντων.

Είσοδος

Η είσοδος θα περιέχει έναν αριθμό αρχείων ελέγχου. Κάθε αρχείο ελέγχου θα ξεκινά με μια γραμμή που περιέχει τρεις ακέραιους ~X~, ~Y~ και ~P~, όπου ~X~, ~Y~ είναι οι διαστάσεις της περιοχής ~(1 \le X,Y \le 30)~ και ~P\;(P \le 10)~ είναι η μέγιστη χωρητικότητα των ξύλων. Στη συνέχεια, θα ακολουθούν ~X~ γραμμές, όπου κάθε μία περιέχει ~Y~ χαρακτήρες. Αυτές οι γραμμές δεν περιέχουν κενά διαστήματα ή οποιουσδήποτε άλλους χαρακτήρες εκτός από αστερίσκο (*), τίλντα (~), τελεία (.), παπάκι (@) και hashtag (#). Το πολύ 50% της συνολικής περιοχής θα περιέχει ανθρώπους. Η είσοδος θα τερματίσει με EOF. Θα υπάρχει μια κενή γραμμή μεταξύ δύο διαδοχικών αρχείων ελέγχου.

Έξοδος

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

Παράδειγμα

input

3 4 2
*~~#
...@
.~.*

3 5 1
~~*~~
#.@.#
~~*~~

1 4 2
**#~

output

2
2
1