مهرزاد عاشق ادبیات و شاعری است. او هر شب از ساعت ۲۱:۰۰ الی ۲۱:۳۰ به برنامه‌ی «مشاعره» که از رادیو فرهنگ پخش می‌شود گوش می‌کند. دیشب مرتباً امواج کانال رادیو جوان روی کانال رادیو فرهنگ می‌افتاد و باعث شد که مهرزاد بین اشعار (یا به‌صورت ساده‌تر، کلماتِ) مشاعره، کلماتی از رادیو جوان را نیز بشنود!

مهرزاد تمام کلماتی را که دیشب از طریق رادیو شنیده، دقیقاً به‌همان ترتیب، روی یک تکّه کاغذ نوشته است. او می‌خواهد بداند تعداد کلماتی که مربوط به برنامه‌ی «مشاعره» بوده است، در بهترین حالت حداکثر چند کلمه است؟

به عبارت دقیق‌تر او می‌خواهد زیردنباله‌ای (یک زیردنباله‌ی $S'$ از یک دنباله‌ی $S$، دنباله‌ای است که با حذف تعدادی از عناصر $S$ و حذف ترتیب نسبی سایر عناصر به‌دست می‌آید) از دنباله‌ی کلمات ورودی را پیدا کند که اوّلاً طول آن بیشینه باشد، ثانیاً حرف اوّل هر کلمه از این دنباله (به‌جز کلمه‌ی اوّل)، مشابه حرف آخر کلمه‌ی قبلی‌اش باشد.

• در سطر اوّل ورودی، تعداد سناریوهای تست آمده است.
• سپس در ابتدای هر سناریو، عدد $n$ (تعداد کلمات) آمده است.
• در هر یک از $n$ سطر بعدی، در هر سطر یک کلمه با حروف بزرگ انگلیسی نوشته شده است.
• همواره $1 \le n \le 10^5$ و در ۴۰ درصد تست‌ها، در تمام سناریوها $1\le n\le 10^3$.
• طول کلمات ورودی حداقل یک حرف و حداکثر ۲۰ حرف است. این کلمات الزاماً فقط از حروف بزرگ الفبای انگلیسی تشکیل شده‌اند.
• $\le 20$ تعداد سناریوها $1 \le$.

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

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