Counting Good DNA Triples

You are given n DNA sequences \( S_1, S_2, \dots, S_n \) where each sequence is represented as a string containing only the four uppercase letters \( A \), \( C \), \( G \), and \( T \).

A concatenation operation between two DNA sequences \( S_i \) and \( S_j \) is defined as taking any prefix (possibly empty) of \( S_i \) and any suffix (possibly empty) of \( S_j \) and concatenating them. For example, if \( S_i = \texttt{ACGC} \) and \( S_j = \texttt{CTAT} \), then some possible concatenations are \( \texttt{ACGCTAT} \), \( \texttt{ACGCCTAT} \), \( \texttt{ACAT} \), and \( \texttt{T} \).

A triple \( (i,j,k) \) (with \( 1\le i,j,k\le n \)) is called good if and only if \( i\neq k \), \( j\neq k \) and the sequence \( S_k \) can be obtained by concatenating some prefix of \( S_i \) with some suffix of \( S_j \). The task is to count the number of good triples \( (i,j,k) \).

The mathematical condition for \( S_k \) to be obtained from \( S_i \) and \( S_j \) is as follows: there exists an integer \( p \) with \( 0 \le p \le |S_k| \) such that:

[ \begin{aligned} &p \le |S_i|, \quad |S_k|-p \le |S_j|, \ &S_i[0:p] = S_k[0:p] \quad \text{and} \quad S_j[|S_j|-(|S_k|-p):|S_j|] = S_k[p:|S_k|]. \end{aligned} ]

Your task is to count the number of triples \( (i,j,k) \) satisfying the above conditions.

inputFormat

The first line contains a single integer \( n \) (the number of DNA sequences). Each of the following \( n \) lines contains a non-empty string representing a DNA sequence.

outputFormat

Output a single integer denoting the count of good triples \( (i, j, k) \) that satisfy the conditions.

sample

3
AC
GT
ACT

1