Tổng Độ Dài Tiền Tố Chung

Tính tổng độ dài tiền tố chung dài nhất của mọi cặp chuỗi ở hai vị trí khác nhau trong danh sách.

Với hai chuỗi $x$ và $y,\mathrm{LCP}(x,y)$ là độ dài đoạn đầu dài nhất mà hai chuỗi giống nhau hoàn toàn. Mỗi cặp vị trí $i<j$ được tính đúng một lần, kể cả khi $S_i$ và $S_j$ có cùng nội dung.

Input

• Dòng đầu chứa số nguyên $N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa chuỗi $S_i$; hai dòng có thể chứa chuỗi giống nhau.

Output

• In một số nguyên duy nhất là tổng $\mathrm{LCP}(S_i,S_j)$ với mọi $1\le i<j\le N$.

Constraints

• $2\le N\le 3\cdot 10^5$.
• Mỗi $S_i$ là một chuỗi không rỗng chỉ gồm các chữ cái thường $a,\dots ,z$.
• Tổng độ dài của $N$ chuỗi không vượt quá $3\cdot 10^5$.
• $\mathrm{LCP}(x,y)$ là số ký tự liên tiếp giống nhau tính từ đầu hai chuỗi; giá trị có thể bằng $0$ và bằng toàn bộ độ dài chuỗi ngắn hơn.
• Kết quả có thể vượt quá phạm vi số nguyên $32$ bit; cần dùng kiểu số nguyên $64$ bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 2000$ và tổng độ dài các chuỗi không vượt quá $5000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
sun
sum
s
moon
sun

10