给定一组 n 个字符串:s1、s2、...、sn。
您应该找到该群的子群 si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n)。必须满足以下两个条件:
- 存在一个字符串 t,找到的子组中的每个字符串都是其后缀;
- 找到的子组中的字符串数量尽可能多。
您的任务是打印找到的子组中的字符串数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 组中字符串的数量。接下来的 n 行中的每一行都包含一个字符串。第 i 行包含非空字符串 si。
每个字符串仅由小写拉丁字母组成。所有字符串 si 的总和不超过 105。
输出
输出一个整数 — 找到的子组中的字符串数量。
示例
输入 #1
6 bb bb b aaa aa z
输出 #1
3
注意
查看测试样本。所需的子组是 s1、s2、s3。