• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

ممل علیشو مجبور کرده که \(n\) تا رشته از حروف کوچک انگلیسی رو، رو یه کاغذ بنویسه. ممل می‌خواد این کاغذو بذاره جلو پاشا و بهش بگه با این کلمه‌ها یه رشته‌ی پالیندروم(رشته ای که خودش با برعکس برابره مثل abba) بنویسه.

پاشا باید حداقل یکی از این رشته‌هارو استفاده کنه و می‌تونه یه رشته رو چند بار استفاده کنه و به هر ترتیبی که خواست اونارو بچسبونه به هم و بنویسه و نتیجه باید رشته‌ای پالیندروم بشه.

ممل به تعداد حروفی که پاشا در رشته آخر نوشته علیشو می‌زنه. علیش رشته‌هایی که نوشته بودو یادشه و می‌خواد بدونه حداقل چند بار کتک می‌خوره. حداقل تعداد کتک‌هایی که علیش می‌خوره چند تاست؟‌ اگه پاشا نتونه رشته پالیندروم بسازه ممل علیشو ماچ می‌کنه که معادل -1 بار(!) کتک خوردنه.

ورودی

در خط اول \(n\)، و در \(n\) خط بعدی رشته هایی که علیش نوشته آمده. تضمین می‌شود رشته‌ها فقط از حروف کوچک انگلیسی تشکیل شده باشند و جمع طول آنها حداکثر \(3\ 000\) باشد.

\[1 \le n \le 3\ 000\]

خروجی

در خروجی تنها حداقل تعداد بار‌هایی که علیش کتک می‌خوره رو چاپ کنید.

مثال

ورودی نمونه ۱

3
ps
as
sp

خروجی نمونه ۱

4

• رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داره pssp است.

ورودی نمونه ۲

4
abb
ba
bba
abaa

خروجی نمونه ۲

5

• رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داشته باشه abbba است.

ورودی نمونه ۳

3
abbs
sbbx
we

خروجی نمونه ۳

-1

• پاشا نمی‌تونه رشته پالیندرومی بسازه.