你的弟弟妹妹沉迷于一首相当重复的歌曲。他们声称这首歌并不重复，因此你决定通过找出这首歌中最长（按单词数量计算）的子序列来证明你的观点，使得你的弟弟妹妹无法在完整的歌词中明确地识别出该子序列。

更正式地说，一个长度为 $\ell$ 的歌曲子序列（歌曲共有 $n$ 个单词）是一个由 $\ell$ 个整数组成的元组 $1 \le s_1 < s_2 < \dots < s_\ell \le n$，用于标识子序列中的单词。如果存在另一个长度为 $\ell$ 的子序列 $1 \le t_1 < t_2 < \dots < t_\ell \le n$（且对于至少一个索引 $i$ 满足 $s_i \neq t_i$），使得歌曲中第 $s_1$ 个单词与第 $t_1$ 个单词相同，第 $s_2$ 个单词与第 $t_2$ 个单词相同，以此类推，那么该子序列就是“不可明确识别的”。

给定一首歌的歌词，输出最长的不可明确识别子序列的长度。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示歌词中的单词数量。 接下来的 $n$ 行，每行包含一个歌词单词，按顺序给出。每个单词由最多 20 个大写字母 (A–Z) 和小写字母 (a–z) 组成。同一个单词可能出现在多行中。如果两个单词不完全匹配（包括大小写），则它们被视为不同的单词。

输出格式

输出一个整数 $\ell$，表示最长的不可明确识别歌曲子序列的单词数量。如果这首歌的所有子序列都是可明确识别的，则输出 0。在确定子序列是否可明确识别时，如果两个单词的对应字符完全相同，则视为相同（换句话说，区分大小写）。

样例

样例输入 1

10
bow
bow
chick
chicka
chicka
bow
bow
chick
chicka
chicka

样例输出 1

9

样例输入 2

31
head
shoulders
knees
and
toes
knees
and
toes
head
shoulders
knees
and
toes
knees
and
toes
eyes
and
ears
and
mouth
and
nose
head
shoulders
knees
and
toes
knees
and
toes

样例输出 2

29