Sinulle on annettu n \times n -kokoinen ruudukko, jonka jokainen ruutu on tyhjä, tai siinä on kolikko. Aloitat ruudukon vasemmasta yläkulmasta. Saat liikkua joka siirrolla askeleen oikealle tai alaspäin, mutta et ruudukon ulkopuolelle. Jos olet ruudussa, jossa on kolikko, se lisätään saldoosi.

Mikä on suurin mahdollinen kolikoiden saldo, kun saavut ruudukon oikeaan alareunaan?

Syöte

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

Tämän jälkeen syötteessä on ruudukon kuvaus. Jokainen ruutu on tyhjä (.) tai siinä on kolikko (o).

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen saldo.

Rajat

• 1 \le n \le 30

Esimerkki

Syöte:

3
..o
..o
o..

Tuloste:

2