Problem Description

Qiyue has $n$ DNA base sequences $S_1, S_2, \dots, S_n$, each of which can be represented as a string consisting only of the uppercase letters A, C, G, and T.

Qiyue can combine two DNA base sequences by attaching a prefix (which can be empty) of the first sequence to a suffix (which can be empty) of the second sequence. For example, combining ACGC with CTAT might result in ACGCTAT, ACGCCTAT, ACAT, or T.

Qiyue defines a triplet $(i, j, k)$ as "good" if and only if $1 \le i, j, k \le n$, $i \ne k$, $j \ne k$, and $S_i$ combined with $S_j$ can yield $S_k$.

Qiyue wants to know the number of good triplets.

Input Format

The first line contains an integer $n\ (3 \le n \le 2 \times 10^5)$, representing the number of base sequences.

The following $n$ lines each contain a string, where the $i$-th string defines the base sequence $S_i\ (1 \le |S_i| \le 2 \times 10^6)$. It is guaranteed that $\sum |S_i| \le 2 \times 10^6$.

Output Format

Output a single integer, which is the number of good triplets.

Sample Input and Output

Sample Input #1

3
AAA
AA
AA

Sample Output #1

12

Sample Input #2

3
ACGC
CTAT
ACAT

Sample Output #2

1

Sample Input #3

4
A
C
T
G

Sample Output #3

0

见题面 Input 部分

见题面 Output 部分