Niitty koostuu n \times n ruudusta. Jokaisessa ruudussa kasvaa tietyn lajinen kukka. Mahdolliset kukkalajit vastaavat kirjaimia A–Z, mutta kaikki lajit eivät välttämättä esiinny niityllä.

Haluat aidata niityltä suorakulmaisen alueen. Vaatimuksena on, että alueella kasvaa vähintään yksi kukka jokaista lajia, jota niityllä ylipäätään esiintyy.

Kuinka monta mahdollista aitausta on?

Syöte

Ensimmäisellä rivillä on kokonaisluku n: niityn sivun pituus.

Seuraavat n riviä kuvaavat niityn kukkalajit. Jokaisella rivillä on merkeistä A–Z koostuva merkkijono, jonka pituus on n.

Tuloste

Tulosta mahdollisten aitausten määrä.

Esimerkki

Syöte:

4
AAAK
ABAA
ABAA
AAAA

Tuloste:

6

Kelvolliset aitaukset on merkitty kuvaan punaisella.

Osatehtävä 1 (4 pistettä)

• 1 \le n \le 10

Osatehtävä 2 (6 pistettä)

• 1 \le n \le 20

Osatehtävä 3 (10 pistettä)

• 1 \le n \le 50

Osatehtävä 4 (13 pistettä)

• 1 \le n \le 100

Osatehtävä 5 (25 pistettä)

• 1 \le n \le 200

Osatehtävä 6 (42 pistettä)

• 1 \le n \le 500