====== مشاعره ====== مهرزاد عاشق ادبیات و شاعری است. او هر شب از ساعت ‎۲۱:۰۰‎ الی ‎۲۱‎:۳۰ به برنامه‌ی ‎«مشاعره»‎ که از رادیو فرهنگ پخش می‌شود گوش می‌کند. دیشب مرتباً امواج کانال رادیو جوان روی کانال رادیو فرهنگ می‌افتاد و باعث شد که مهرزاد بین اشعار (یا به‌صورت ساده‌تر، کلمات‎ِ) مشاعره، کلماتی از رادیو جوان را نیز بشنود‎!‎ مهرزاد تمام کلماتی را که دیشب از طریق رادیو شنیده، دقیقاً به‌همان ترتیب، روی یک تکّه کاغذ نوشته است. او می‌خواهد بداند تعداد کلماتی که مربوط به برنامه‌ی ‎«مشاعره»‎ بوده است، در بهترین حالت **حداکثر** چند کلمه است؟ به عبارت دقیق‌تر او می‌خواهد زیردنباله‎‌ای (یک زیردنباله‌ی ‎$S'$‎ از یک دنباله‌ی ‎$S$‎، دنباله‌ای است که با حذف تعدادی از عناصر ‎$S$‎ و حذف ترتیب نسبی سایر عناصر به‌دست می‌آید)‎ از دنباله‌ی کلمات ورودی را پیدا کند که اوّلاً طول آن بیشینه باشد، ثانیاً حرف اوّل هر کلمه از این دنباله (به‌جز کلمه‌ی اوّل)، مشابه حرف آخر کلمه‌ی قبلی‌اش باشد. ===== ورودی ===== * در سطر اوّل ورودی، تعداد سناریوهای تست آمده است. * سپس در ابتدای هر سناریو، عدد ‎$n$ (تعداد کلمات) آمده است. * در هر یک از ‎$n$‎ سطر بعدی، در هر سطر یک کلمه با حروف بزرگ انگلیسی نوشته شده است. * همواره ‎$1 \le n \le 10^5$‎ و در ‎۴۰‎ درصد تست‌ها، در تمام سناریوها ‎$1\le n\le 10^3$‎. * طول کلمات ورودی حداقل یک حرف و حداکثر ‎۲۰‎ حرف است. این کلمات الزاماً فقط از حروف بزرگ الفبای انگلیسی تشکیل شده‌اند. * $\le 20$‎ تعداد سناریوها ‎$1 \le$‎. ===== ‎خروجی ===== برای هر یک از تست‌های ورودی در یک سطر طول طولانی‌ترین زیردنباله‌ی مشاعره‌ای را بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودي و خروجي نمونه ===== ^ ورودي نمونه ^ خروجي نمونه ^ |3 \\ ‎1 \\ ‎HAAFEZAA \\ ‎4 \\ ‎TORANJ \\ ‎JAKOJOONEVAR \\ ‎JAAN \\ ‎NEGAARAA \\ ‎5 \\ ‎ROOZEGAARI \\ ‎TARAANEYEMAADARI \\ ‎INGOMGASHTE| ‎1 \\ 3 \\ 3| * [[سوال ۸|سوال بعد]] * [[سوال ۶|سوال قبل]]