You are given n strings
Find the size of the largest subset of these n strings such that all the strings in the chosen subset have some common prefix (at least of length 1) as well as some common suffix (at least of length 1).
A prefix of a string S is a substring of S that occurs at the beginning of S. A suffix of a string S is a substring that occurs at the end of S.
Output the size of the largest such subset.
Note that the chosen subset can have a single string also.
Input format
The first line contains a single integer n (1≤ n ≤ 100000) — the number of strings.
The next n lines contain a string
Output format
Print the size of the largest subset
Constraints
1≤n≤105
3 ≤ length of each string ≤10
The largest subset consists of following strings { "bbbbbbb" , "bbbcbbb" , "bbbdbbb" } . All the chosen strings share "bbb" as the common prefix and "bbb" as the common suffix.
Hence the output is 3
