Problem Description

Qiyue has $n$ DNA base sequences $S_1, S_2, \dots, S_n$. Each base sequence can be represented as a string containing only the four uppercase letters A, C, G, and T.

Qiyue can splice two DNA base sequences. The specific operation is: take a prefix (possibly empty) of the first sequence and concatenate it with a suffix (possibly empty) of the second sequence. For example, splicing ACGC and CTAT may produce ACGCTAT, ACGCCTAT, ACAT, or T.

Based on this, Qiyue defines that a triple $(i, j, k)$ is good if and only if $1 \le i, j, k \le n$, $i \ne k$, $j \ne k$, and splicing $S_i$ and $S_j$ can produce $S_k$.

Qiyue wants to know the number of good triples.

Input Format

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

The next $n$ lines each contain a string. 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 one integer, representing the number of good triples.

3
AAA
AA
AA

12

3
ACGC
CTAT
ACAT

1

4
A
C
T
G

0

Hint

Translated by ChatGPT 5