Xâu tiền tố

Trong ngôn ngữ học và khoa học máy tính, khái niệm "tiền tố" (prefix) đóng vai trò quan trọng trong nhiều lĩnh vực như xử lý ngôn ngữ tự nhiên, nén dữ liệu, và tìm kiếm thông tin. Một xâu được gọi là tiền tố của xâu khác nếu nó xuất hiện ngay từ đầu của xâu đó, như những chương mở đầu trong một cuốn sách hay những nốt nhạc đầu tiên của một bản giao hưởng.

Xét ví dụ: xâu "tho" là tiền tố của "thơ" và "thơ ca"; xâu "code" là tiền tố của "coder" và "codeforce". Đặc biệt, mọi xâu đều là tiền tố của chính nó, giống như mỗi con người đều bắt đầu từ chính mình.

Bài toán: Trong một thư viện kỹ thuật số lưu trữ \(n\) từ khóa (mỗi từ khóa là một xâu ký tự), ban quản lý muốn phân tích mối quan hệ bao hàm giữa các từ khóa. Cụ thể, họ quan tâm đến việc đếm số cặp từ khóa mà từ khóa này là tiền tố của từ khóa kia. Điều này giúp xây dựng hệ thống gợi ý từ khóa thông minh và tổ chức thông tin khoa học hơn.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\) - số lượng từ khóa trong thư viện.
• \(n\) dòng tiếp theo, mỗi dòng chứa một từ khóa được biểu diễn bằng xâu ký tự chỉ gồm các chữ cái tiếng Anh in thường. Độ dài mỗi từ khóa không vượt quá \(10\) ký tự.

Output

Một số nguyên duy nhất là số lượng cặp từ khóa \((s_i, s_j)\) (với \(i \neq j\)) sao cho \(s_i\) là tiền tố của \(s_j\). Lưu ý rằng cặp \((s_i, s_j)\) và \((s_j, s_i)\) được coi là khác nhau nếu cả hai đều thỏa mãn điều kiện.

Example

4
abc
aa
aab
aa

4

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(n \le 10^3\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(10^3 < n \le 10^5\).
• \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.