K. Pick a Pair
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Friends play an interesting game with words. The goal of this game is arranging words in pairs.

Friends have $$$n$$$ words of the same length. They are choosing the largest number $$$k$$$ such that it is possible to divide the words into pairs so that words in each pair have common prefix of length at least $$$k$$$.

Find the maximum possible value of $$$k$$$.

Input

The first line of input contains an even integer $$$n$$$ — number of words ($$$1 \leq n \leq 2\cdot 10^5$$$).

The following $$$n$$$ lines contain words that the friends have. All words have same length. Total words length is less or equal to $$$2 \cdot 10^6$$$.

Output

Output maximal possible value of $$$k$$$.

Examples
Input
4
aabc
aacc
bbbb
bbbd
Output
2
Input
2
a
b
Output
0