Với hai xâu ~x~ và ~y~, hàm ~f(x,y)~ được định nghĩa là độ dài của tiền tố chung dài nhất của hai xâu ~x~ và ~y~.

Cho ~n~ xâu ~s_1,s_2,..,s_n~ chỉ chứa các ký tự chữ cái in thường, bạn hãy tính giá trị biểu thức:

$$\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(s_i,s_j)$$

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ xâu ~s_1,s_2,...,s_n~ chỉ chứa các ký tự chữ cái in thường ~(1 \le |s_i|~ ~;~ ~|s_1|+|s_2|+...+|s_n| \le 3 \times 10^5)~.

Output

• In ra giá trị biểu thức cần tính

Examples

Sample Input 1

3
xy xyz xwz

Sample Output 1

4

Sample Input 2

4
aaaaaaa aaa aaaaa aaaa

Sample Output 2

22

Notes

Trong ví dụ đầu tiên, các giá trị ~f(s_i,s_j)~ như sau:

• ~f(s_1,s_2)=2~
• ~f(s_1,s_3)=1~
• ~f(s_2,s_3)=1~