Друзья играют в интересную игру со словами, суть которой заключается в разбиении слов на пары.
У друзей есть \(n\) слов одинаковой длины. Они хотят выбрать такое наибольшее число \(k\), чтобы можно было разбить слова на пары так, чтобы в каждой паре у слов совпадало хотя бы \(k\) первых букв.
Помогите друзьям найти искомое максимальное значение \(k\).
Формат входных данных
В первой строке входных данных находится целое число \(n\) — количество слов (\(1 \leqslant n \leqslant 2\cdot 10^5\), \(n\) — четное).
В следующих \(n\) строках заданы слова, которые есть у друзей. Гарантируется, что все строки имеют одинаковую длину и суммарная длина строк не превышает \(2 \cdot 10^6\).
Формат выходных данных
В единственной строке выведите число \(k\) — искомое максимальное значение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
aabc
aacc
bbbb
bbbd
|
2
|
|
2
|
2
a
b
|
0
|