+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سرانجام هری‌پاتر توانست طلسم شکست دادن دشمن بزرگ خود مالفوی را ابداع کند! هری یک جفت دستبند قدرت دایره‌ای ساخته که روی مچ دست‌های راست و چپش بسته می‌شود. او روی هر دستبند دنباله‌ای از حروف جادویی نوشته است که هر حرف فعال قدرت او را تقریبا به اندازه یک بید کتک‌زن افزایش می‌دهد! با این حال یک مشکل وجود دارد. دستبندها فقط زمانی کار می‌کنند که زیردنباله حروف فعال شده روی هر دو دستبند یکسان باشد. برای مثال در شکل زیر یک جفت دستبند داده شده که حروف دو رشته $ababdcbcc$ و $aabdccccbd$ به عنوان حروف جادویی روی آنها قرار گرفته است که یک فعال‌سازی بهینه از این حروف به هری قدرتی به اندازه ۱۴ بید کتک‌زن می‌دهد.  روی دستبند اول حروف $babdccc$ در جهت ساعت‌گرد و روی دستبند دوم همین حروف در جهت پادساعت‌گرد فعال شده است. بطور کلی ترتیب حروف مهم است اما جهت زیر دنباله فعال روی هر دستبند (در جهت عقربه‌های ساعت یا خلاف جهت) ممکن است یکسان باشد یا نباشد. فراموش نکنید که دستبندها دایره‌ای هستند! شما باید به هری کمک کنید که تصمیم بگیرد چه زیردنباله بهینه‌ای از حروف روی دستبندهایش را لازم است فعال کند تا بتواند مالفوی را شکست دهد. # ورودی فایل ورودی حداکثر شامل ۱۰۰ نمونه ورودی است. (حداکثر شامل ۵ نمونه بزرگ) هر نمونه یک خط شامل یک جفت رشته که با فاصله جدا شده اند و مربوط به همان دنباله حروف روی دستبندهای قدرت چپ و راست هری است (به ترتیب) می باشد و هر رشته تنها از حروف کوچک تشکیل خواهد شد. طول هر رشته ورودی بین $1$ تا $100$ کاراکتر است به جز در نمونه های بزرگ که طول هر رشته ورودی بین $1$ تا $1500$ کاراکتر می باشد. # خروجی حداکثر قدرتی که هری با فعال کردن حروف روی دستبندها می تواند برسد (بر حسب واحد بید کتک‌زن) را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` ababdcbcc aabdccccbd harrypotter plorppothaa potterharry plorppothaa ``` ## خروجی نمونه ۱ ``` 14 12 12 ```