Sinulle on annettu n \times n -ruudukko, joka kuvaa metsän. Jokaisessa ruudussa on merkki . (tyhjä) tai * (puu).

Haluat rakentaa metsään neliön muotoisen rakennuksen, mutta et halua kaataa mitään puuta rakennuksen takia.

Tehtäväsi on laskea jokaiselle rakennuksen koolle 1 \times 1, 2 \times 2, \dots, n \times n, montako mahdollista paikkaa niin suurelle rakennukselle on metsässä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ruudukon koko.

Sitten syötteessä on n riviä, joista jokaisella on n merkkiä: metsän kuvaus.

Tuloste

Tulosta n kokonaislukua: rakennusten paikkojen määrät.

Rajat

• 1 \le n \le 2500

Esimerkki

Syöte:

3
..*
...
..*

Tuloste:

7 2 0