Giáo sư Nghĩa là nhà nghiên cứu về sinh vật học. Khi nghiên cứu về gen di truyền của các cá thể động vật, mỗi đoạn thông tin về gen của mỗi cá thể được giáo sư ký hiệu bằng một xâu các ký tự liền nhau gồm các chữ cái in thường từ a đến z trong bảng chữ cái tiếng Anh. Hiện tại ông đang nghiên cứu một nhóm động vật có n cá thể, đoạn thông tin gen của các cá thể lần lượt là các xâu ~S_1~,~S_2~,~S_3~,…,~S_n~, độ dài của mỗi xâu là số ký tự trong xâu. Vì một số đoạn thông tin gen có độ dài rất lớn, gây khó khăn cho việc nghiên cứu nên giáo sư quyết định cắt bỏ một số các ký tự cuối của mỗi đoạn (có thể có một đoạn nào đó không bị cắt) sao cho đoạn dài nhất chỉ còn k ký tự nhưng vẫn đảm bảo không có hai đoạn thông tin gen bất kỳ nào giống nhau.

Yêu cầu: Cho n đoạn thông tin gen đôi một khác nhau ~S_1~,~S_2~,…,~S_n~ (n ≤ ~10^5~), độ dài mỗi đoạn lớn hơn hoặc bằng 1, tổng độ dài tất cả các đoạn không vượt quá ~10^6~. Các bạn học sinh giỏi môn Tin học hãy giúp giáo sư Nghĩa tìm giá trị k nhỏ nhất thỏa mãn yêu cầu trên.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ~n~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ (1 ≤ ~i~ ≤ ~n~) chứa xâu gồm các chữ cái latin in thường biểu diễn đoạn gen ~S_i~.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra một số nguyên là giá trị k nhỏ nhất tìm được.

Ví dụ:

INPUT

4
atgxatxgatgx
atgxatat
atgxx
atxgtaaxagttxxgt

OUTPUT

7

*Giải thích: *

Với k=7, ta có các đoạn: "atgxatx", "atgxata", "atgxx", "atxgtaa" đôi một khác nhau.

Ràng buộc:

• Có 30% số test tương ứng 30% số điểm có n ≤ 50,|~S_i~|≤100;
• Có 30% số test khác tương ứng 30% số điểm có 50 < n ≤ 1000,|~S_i~|≤1000;
• 40% số test còn lại tương ứng 40% số điểm có 1000 < n ≤~10^5~.