Nhân xâu

Định nghĩa phép nhân xâu: tích của xâu $s$ có độ dài $m$ với xâu $t$ là xâu

$$s·t=t+s_1+t+s_2+t+\dots +t+s_m+t$$

trong đó $s_i$ là ký tự thứ $i$ của $s$ và dấu $+$ là phép nối xâu. Nói cách khác, ta chèn một bản sao của $t$ vào giữa mỗi hai ký tự liên tiếp của $s$, đồng thời thêm một bản sao ở đầu và một bản sao ở cuối.

Ví dụ, tích của "abc" với "de" là "deadebdecde", còn tích của "ab" với "z" là "zazbz". Khác với phép nhân số, phép nhân xâu không có tính giao hoán: $s·t$ nói chung khác $t·s$.

Độ đẹp của một xâu là độ dài của xâu con liên tiếp dài nhất chỉ gồm một loại ký tự. Chẳng hạn độ đẹp của "xayyaaabca" bằng $3$ (nhờ đoạn "aaa"), còn độ đẹp của "qwerqwer" bằng $1$.

Cho $n$ xâu $p_1,p_2,\dots ,p_n$. Hãy tính độ đẹp của xâu

$$(\dots ((p_1·p_2)·p_3)·\dots )·p_n$$

tức là các phép nhân được thực hiện lần lượt từ trái sang phải.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số lượng xâu.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa xâu khác rỗng $p_i$ gồm các chữ cái latin thường.

Dữ liệu ra

Một số nguyên duy nhất là độ đẹp của tích các xâu.

Ràng buộc

• $2\le n\le 100000$
• Tổng độ dài của tất cả các xâu $p_i$ không vượt quá $100000$
• Dữ liệu đảm bảo độ đẹp của xâu kết quả không vượt quá ${10}^9$

Ví dụ