Problem Description

Xiaolan has $n$ pairwise distinct words $s_1, s_2, \dots, s_n$ in the dictionary. Each word consists only of lowercase letters, and its length does not exceed $20$.

Xiaolan defines an operation: perform exactly one of the following two transformations on a word:

• Insert one lowercase letter at any position.
• Delete any one letter from it.

Except for the inserted or deleted position, the relative order of the original letters remains unchanged.

Now, please count how many ordered word pairs $(s_i, s_j)$ (where $i \ne j$) satisfy: $s_i$ can be transformed into $s_j$ by performing exactly one operation as defined above.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain a string consisting only of lowercase letters, representing a word.

Output Format

Output one line containing one integer, representing the number of ordered word pairs that satisfy the condition.

5
aab
ab
a
bb
b

8

Hint

Sample Explanation

The $8$ ordered word pairs that satisfy the condition are:

• $(aab, ab)$: delete the $1$st letter $a$ from $aab$ to get $ab$.
• $(ab, aab)$: insert the letter $a$ at the $1$st position of $ab$ to get $aab$.
• $(ab, a)$: delete the $2$nd letter $b$ from $ab$ to get $a$.
• $(a, ab)$: insert the letter $b$ at the $2$nd position of $a$ to get $ab$.
• $(ab, b)$: delete the $1$st letter $a$ from $ab$ to get $b$.
• $(b, ab)$: insert the letter $a$ at the $1$st position of $b$ to get $ab$.
• $(bb, b)$: delete the $1$st letter $b$ from $bb$ to get $b$.
• $(b, bb)$: insert the letter $b$ at the $1$st position of $b$ to get $bb$.

Constraints

For $30\%$ of the testdata, $1 \leq n \leq 100$.

For all testdata, $1 \leq n \leq 10000$. It is guaranteed that all words are pairwise distinct.

Translated by ChatGPT 5