Merkkijonot A ja B ovat harmoniset, jos ne ovat yhtä pitkät ja seuraavat ehdot pätevät kaikissa kohdissa:

1. Jos A:n kahdessa kohdassa on sama merkki, niin myös B:n vastaavissa kohdissa on sama merkki.
2. Jos A:n kahdessa kohdassa on eri merkki, niin myös B:n vastaavissa kohdissa on eri merkki.

Sinulle annetaan lista, jossa on n merkkijonoa, ja tehtäväsi on laskea harmonisten merkkijonoparien määrä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: merkkijonojen määrä.

Tämän jälkeen syötteessä on n riviä, joista jokaisella on yksi merkkijono. Jokainen merkkijono muodostuu merkeistä A–Z ja siinä on enintään 50 merkkiä.

Tuloste

Tulosta yksi kokonaisluku: harmonisten merkkijonoparien määrä.

Esimerkki

Syöte:

6
AAB
ABKA
SSG
TSGT
ZZZZ
KEAK

Tuloste:

4

Selitys: Harmoniset parit ovat (AAB, SSG), (ABKA, TSGT), (ABKA, KEAK) ja (TSGT, KEAK).

Osatehtävä 1 (15 pistettä)

• 1 \le n \le 20

Osatehtävä 2 (31 pistettä)

• 1 \le n \le 5000

Osatehtävä 3 (54 pistettä)

• 1 \le n \le 10^5