Tekstide erinevus

문제

Kuulus tarkvarafirma Interplanetary Software Systems on loomas uut tekstitoimetit, mis suudab töödelda väga pikki väikestest ladina tähtedest koosnevaid ridu. Toote esimesel versioonil on ainult kaks funktsiooni:

1. tähe lisamine rea lõppu;
2. rea viimase tähe kustutamine (kui rida ei ole tühi).

Nimetame kahe sõne $ss$ ja $tt$ erinevuseks $\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(s,t)\backslash mathrm\{diff\}(s,\; t)$ minimaalset sõnest $ss$ sõne $tt$ saamiseks vajalike käskude arvu. Näiteks $\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(\backslash mathrm\{diff\}($'tests','text'$)=5)\; =\; 5$: algul kustutame sõne 'tests' lõpust kolm viimast tähte ja seejärel lisame tulemuse lõppu tähed 'x' ja 't'.

Kirjutada programm, mis antud $NN$ sõne $S_{i}S\_i$ kohta leiab $\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(S_i,S_j)\backslash mathrm\{diff\}(S\_i,\; S\_j)$ summa üle kõigi paaride, kus $1\le i\le N1\; \backslash le\; i\; \backslash le\; N$ ja $1\le j\le N1\; \backslash le\; j\; \backslash le\; N$.

입력

Faili esimesel real on tekstiridade arv $NN$ ($1\le N\le 2000001\; \backslash le\; N\; \backslash le\; 200\backslash ,000$) ja järgmisel $NN$ real igaühel üks väikestest ladina tähtedest koosnev mittetühi sõne $S_{i}S\_i$. On teada, et $S_{i}S\_i$ pikkuste summa ei ületa ${10}^{6}10^6$.

출력

Faili ainsale reale väljastada otsitav erinevuste summa.