Minheejin

Interview

Time limit1sMemory limit512 MB

Summary

Given N names, count the pairs of people where a non-empty suffix of one name matches a prefix of the other.

Level: Easy3 of 10
Topics: String, String matching, Brute force
Solved: No attempts yet

Problem

Connecting Lee Minhee and Minhee Jin gives Lee Minheejin

Connecting Kim Seoin and Seo-in Guk gives Kim Seoin-guk

Connecting Park Geon and Geonppang gives Park Geonppang

Minhee enjoys connecting two people when the back part of one person's name matches the front part of the other person's name.

Given $N$ people, find the number of distinct pairs of people that can be connected.

Two people with names $S$ and $T$ can be connected if there is a positive integer $k$ with $k \leq$ the length of $S$ and the length of $T$ such that either the first $k$ letters of $S$ match the last $k$ letters of $T$ , or the last $k$ letters of $S$ match the first $k$ letters of $T$ .

Input

The first line contains the number of people $N$ . $\left(1 \leq N \leq 100\right)$

From the second line onward, each of the next $N$ lines contains one person's name.

Each name consists only of lowercase English letters and has a length of at least 1 and at most 20.

Some people may share the same name.

Output

On the first line, print the number of distinct pairs of people that can be connected.

Examples3

Example 1
Input
```
2
yunny
yeony
```
Expected output
```
1
```
Example 2
Input
```
3
leeminhee
minheejin
jinmichae
```
Expected output
```
2
```
Example 3
Input
```
4
mini
minhee
minimini
minigimbob
```
Expected output
```
3
```