+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ممل علیشو مجبور کرده که $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 ``` \**پاشا نمی‌تونه رشته پالیندرومی بسازه.