Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. String Distance

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputSuppose you are given two strings $$$a$$$ and $$$b$$$. You can apply the following operation any number of times: choose any contiguous substring of $$$a$$$ or $$$b$$$, and sort the characters in it in non-descending order. Let $$$f(a, b)$$$ the minimum number of operations you have to apply in order to make them equal (or $$$f(a, b) = 1337$$$ if it is impossible to make $$$a$$$ and $$$b$$$ equal using these operations).

For example:

- $$$f(\text{ab}, \text{ab}) = 0$$$;
- $$$f(\text{ba}, \text{ab}) = 1$$$ (in one operation, we can sort the whole first string);
- $$$f(\text{ebcda}, \text{ecdba}) = 1$$$ (in one operation, we can sort the substring of the second string starting from the $$$2$$$-nd character and ending with the $$$4$$$-th character);
- $$$f(\text{a}, \text{b}) = 1337$$$.

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_k$$$ having equal length. Calculate $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of strings.

Then $$$n$$$ lines follow, each line contains one of the strings $$$s_i$$$, consisting of lowercase Latin letters. $$$|s_1| = |s_2| = \ldots = |s_n|$$$, and $$$n \cdot |s_1| \le 2 \cdot 10^5$$$. All these strings are pairwise distinct.

Output

Print one integer: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

Examples

Input

4 zzz bac abc acb

Output

4015

Input

2 a b

Output

1337

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/12/2021 14:49:10 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|