Anh nông dân John có \(N\) con bò, mỗi con bò có một mã định danh khác nhau được viết dưới dạng chuỗi bit (chuỗi được tạo thành từ 2 loại kí tự '0' và '1'). Bessie là cô bò lớn tuổi nhất, cô nhớ mã định danh của tất cả con bò khác và thích đi lại trong trang trại để hỏi về mã định danh của chúng.

Khi một con bò được hỏi về mã định danh, nó sẽ bắt đầu trả lời chuỗi bit định danh của mình, tuy nhiên nó có thể quên phần sau của chuỗi và dừng lại trước khi trả lời đủ mã định danh của mình. Mỗi khi Bessie nghe được một chuỗi bit, nếu đó không phải là mã định danh của bất kỳ con bò nào trên trang trại, thì cô ấy sẽ nhún vai và đi khỏi. Tuy nhiên, nếu đó vô tình là mã định danh của một con bò khác mà không phải con bò cô ấy đang hỏi, thì cô ấy sẽ cho rằng đã xảy ra hành vi đánh cắp danh tính và đưa trang trại vào tình trạng phong tỏa. Lưu ý rằng điều này có thể xảy ra ngay cả khi con bò nói đầy đủ mã định danh của nó.

John cảm thấy mệt mỏi vì tình trạng này nên muốn ngăn chặn nó xảy ra. Anh sẵn sàng thay đổi mã định danh của các con bò bằng cách thêm một số bit vào đó. Trong một giây, anh có thể thêm một bit vào cuối mã định danh của bất kỳ con bò nào. Hãy tính toán thời gian ít nhất để anh ngăn chặn được việc phong tỏa trang trại.

Input

• Dòng đầu tiên chứa \(N\), là số lượng con bò trên trang trại của nông dân John.
• \(N\) dòng tiếp theo, dòng thứ \(k\) chứa một chuỗi bit là mã định danh của con bò thứ \(k\).
• Dữ liệu đảm bảo không có mã định danh nào là chuỗi rỗng và tổng dộ dài của tất cả mã định danh không quá \(10^6\).

Output

• Gồm một số tự nhiên duy nhất là số giây tối thiểu mà John cần dành ra để đảm bảo rằng việc phong tỏa sẽ không bao giờ xảy ra.

Scoring

• Subtask \(1\): Tất cả các mã định danh có độ dài chính xác là \(1\).
• Subtask \(2\): \(N \leq 10^2\) và tổng độ dài của các mã định danh không vượt quá \(10^3\).
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

3
1
1
1

5

3
1
11
111

2

3
1
1
11

4

5
0
01
0011
010
01

6

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

41