Background

Special for beginners, ^_^

Description

有n个仅包含小写字母的字符串。 从这些字符串中选出一个子序列并且满足以下条件：

1.在这个子序列中前一个字符串是后一个字符串的前缀；

2.子序列的长度最大。

请输出这个最大长度。

Format

Input

第一行为字符串的数量N（$\le200000$）。

下面每行一个字符串。.

Output

输出共一行，一个整数，表示满足题意的子序列的长度。

Samples

5
i
int
integer
intern
internet

4

Limitation

1s, 1024KiB for each test case.