Troyangles

Ο Troy λατρεύει τα τρίγωνα. Του αρέσει ιδιαίτερα να μετράει τρίγωνα. Έχει ένα πλέγμα ~N~ επί ~N~ που αποτελείται από χαρακτήρες είτε "." ή "#". Βοηθήστε τον να μετρήσει τον αριθμό των τριγώνων που σχηματίζονται μόνο από χαρακτήρες "#" στο πλέγμα. Τα τρίγωνα είναι της μορφής

                  #
         #       ###
    #,  ###,    #####, κτλ.

Πιο τυπικά, ένα τρίγωνο ύψους ~h~ αποτελείται από ~h~ σειρές για κάποιο θετικό ακέραιο αριθμό ~h~. Η ~i~-οστη σειρά περιέχει ~2i - 1~ "#" χαρακτήρες για ~i = 1, ... , h~. Οι σειρές είναι κεντραρισμένες η μία πάνω από την άλλη έτσι ώστε να είναι συμμετρικά ως προς μια κάθετη γραμμή που περνά από τη μέση τους.

Είσοδος

Η πρώτη γραμμή περιέχει τον αριθμό ~N~ (~1 \le N \le 2\,000~) που αντιπροσωπεύει το μέγεθος του πλέγματος. Οι επόμενες ~N~ γραμμές καθεμία περιέχουν ~N~ χαρακτήρες όπως περιγράφεται παραπάνω.

Βαθμολογία

Μπορείτε να υποθέσετε ότι για τις περιπτώσεις δοκιμής αξίας του 20% της βαθμολογίας, ~N \le 50~.

Έξοδος

Εκτυπώστε τον αριθμό των τριγώνων στο πλέγμα.

Παράδειγμα

input

5
. . . . .
. # # # .
. # # # .
# # # # #
. . . . .

output

16

Επεξήγηση του παραδείγματος

Υπάρχουν ~11~ τρίγωνα ύψους ~1~, ~4~ τρίγωνα ύψους ~2~ και ~1~ τρίγωνο ύψους ~3~.