Annettuna on $n \times n$ -kokoinen ruudukko, jossa jokainen ruutu joko on tyhjä tai sisältää kolikon. Lähdet liikkeelle ruudukon vasemmasta ylänurkasta ja siirryt joka askeleella valintasi mukaan ruudun alaspäin tai oikealle, kunnes olet ruudukon oikeassa alanurkassa.

Montako eri kolikkomäärää voit kerätä ruudukosta reittisi varrelta?

Syöte

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

Tämän jälkeen on $n$ riviä, joista jokaisella on $n$ merkkiä. Jokainen merkki on . (tyhjä ruutu) tai o (kolikko).

Tuloste

Tulosta yksi kokonaisluku: montako eri kolikkomäärää voit kerätä.

Esimerkki

Syöte:

4
..o.
....
.o.o
....

Tuloste:

3

Selitys: voit kerätä 0, 1 tai 2 kolikkoa, joten eri kolikkomääriä on 3.

Osatehtävä 1 (16 pistettä)

• $1 \le n \le 10$

Osatehtävä 2 (30 pistettä)

• $1 \le n \le 100$

Osatehtävä 3 (54 pistettä)

• $1 \le n \le 1000$