Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Các vị vua của đất nước X tin rằng tên của một người rất quan trọng. Vì vậy, tên của các vị vua luôn rất dài, càng dài càng tốt. Tuy nhiên, đây cũng là điều bất tiện, vì vậy để đỡ tốn sức họ thường viết tắt tên của họ lại. Tên viết tắt được ghép từ các chữ cái đầu tiên, ví dụ An Soi Phun Ra Lua, viết tắt là asprl.

Đất nước X qua các triều đại có các vị vua thay thế nhau, tất cả họ đều tuân theo một truyền thống thông thường. Truyền thống đó quy định tên viết tắt của vị vua kế nhiệm có chữ cái đầu tiên giống chữ cái cuối cùng trong tên viết tắt của người tiền nhiệm mình. Để có được sự ổn định lâu dài, truyền thống này không bao giờ bị phá vỡ. Ngoài ra, đất nước này còn có một truyền thống khác nữa. Trong suốt lịch sử của đất nước sẽ có nhiều triều đại, và chữ cái đầu tiên trong tên viết tắt của vị vua đầu tiên của một triều đại trùng với chữ cái cuối trong tên viết tắt của vị vua cuối cùng trong triều đại đó. 

Cách đặt tên của các triều đại rất đơn giản, bằng cách viết tất cả tên các vị vua trong triều đại đó theo thứ tự thời gian. Ví dụ, một triều đại có đời vua “ab” và “ba” thì triều đại là “abba”. Triều đại chỉ có một vua “abca” gọi là “abca”.

LVL là một nhà sử học và đang có trong tay tên viết tắt của tất cả vị vua của đất nước X và người thân của họ, bạn hãy giúp LVL tìm tên triều đại dài nhất có thể của đất nước X nhé.

Danh sách được xếp theo thứ tự thời gian. Nếu tên A đừng trước tên B và A, B là vua thì A cai trị trước B.

Input

Dòng đầu tiên chứa số nguyên n (1 <=n  <= 5.10^5) số lượng tên trong danh sách của nhà sử học (có cả tên của những người không phải là vua).

N dòng tiếp theo, dòng thứ i chứa tên thứ i, mỗi cái tên không quá 10 kí tự.

Output

Dòng duy nhất, tên dài nhất có thể của triều đại trong đất nước X.

Example

Test 1:

Input:

3

abc

ca

cba

Output:

6

Test 2:

Input:

4

vvp

vvp

dam

vvp

Output:

0

Test 3:

Input:

3

ab

c

def

Output:

1

Giải thích test 1:

Có thể có 2 triều đại:

“abcca” ( gồm tên 1 và tên 2)  hoặc “abccba” ( gồm tên 1 và tên 3).

Giải thích test 2: Không thể có cách nào thỏa mãn để có một triều đại.

Giải thích test 3: Có một vị vua duy nhất và triều đại duy nhất  “c”.