Given a function $f(s, t)$ which takes two string $s$ and $t$ as input. Without loss of generality that $|s| \le |t|$, let's say the output of the function is as follow:
$$
\begin{equation}
f(s, t)=\begin{cases}
0, & \text{if $s$ is a prefix of $t$}.\\\\
\text{the first position where $s$ and $t$ differ}, & \text{otherwise}.
\end{cases}
\end{equation}
$$
For example, $f(\text{abc}, \text{abd}) = 3$.
Given a $n$ string $S_i$. Calculate:
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(S_i,S_j)
$$
### Input
- The first line contains an integer $n$.
- The next $n$ lines, each line contains a string $S_i$, each string contains only lowercase letters.
### Output
- Print the value.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le \sum{|S_i|} \le 10^6$
### Example
Input:
```
4
cat
hat
mat
sir
```
Output:
```
6
```
