Loda Teleportations

Time limit1sMemory limit64 MB

Summary

Given N strings in order, find the longest subsequence where each earlier string is both a prefix and a suffix of the later one.

Level: Medium6 of 10
Topics: Dynamic programming, String matching, Hash map
Solved: No attempts yet

Problem

The Solar system has eight planets and one dwarf planet. There is one more fact about it that few people know. A secret planet S4 exists, and small creatures that look like bears live on it. Their codename is Loda. The fact is kept away from the public, but the association Savez sent a team led by general Henrik to study the Lodas. The team found that a Loda can teleport, and Henrik wants to hire the Lodas for his army.

One Loda consists of $N$ strings. Let the $i$ -th string be $x_i$ . The number of teleportations a Loda makes is decided by one special subsequence of these strings. The subsequence does not have to be consecutive. Two strings $x_i$ and $x_j$ with $i < j$ can both belong to that subsequence if and only if $x_j$ starts with $x_i$ and also ends with $x_i$ . The number of teleportations is the length of the longest subsequence that satisfies the condition.

Determine the number of teleportations.

Input

The first line contains the integer $N$ , the number of strings. Each of the next $N$ lines contains one string. Every string consists of uppercase letters of the English alphabet. The total length of all strings is less than two million.

Output

Print the number of teleportations a Loda makes.

Notes

The prefix and the suffix may overlap. For example, AAA starts with AA and ends with AA.

Strings in the subsequence may be equal to each other.

Examples6

Example 1
Input
```
5
A
B
AA
BBB
AAA
```
Expected output
```
3
```
Example 2
Input
```
5
A
ABA
BBB
ABABA
AAAAAB
```
Expected output
```
3
```
Example 3
Input
```
6
A
B
A
B
A
B
```
Expected output
```
3
```
Example 4
Input
```
1
Z
```
Expected output
```
1
```
Example 5
Input
```
5
ABC
ABC
ABC
ABC
ABC
```
Expected output
```
5
```
Example 6
Input
```
5
A
AA
AAA
AAAA
AAAAA
```
Expected output
```
5
```