- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک شرکت \(n\) برنامهنویس مشغول به کار هستند. هر کدام از این \(n\) نفر در برخی از زمینههای Front-end، Back-end یا Product Mangement تخصص دارد.
تخصصهای هر شخص با یک رشته شامل حروف B، F و P به صورت مرتبشده الفبایی به ما داده شده است.
میخواهیم با داشتن این تخصصها، حداکثر تعدادی تیم کامل را تشکیل دهیم. منظور از یک تیم کامل تیمی است که در آن برای هر کدام از این سه زمینه حداقل یک متخصص وجود داشته باشد (ممکن است یک نفر باعث برطرف شدن نیاز چند تخصص باشد). توجه کنید باید در این تیمبندی هر شخص در حداکثر یک تیم آمده باشد.
حال از شما میخواهیم برنامهای بنویسید که این بیشترین تعداد تیم را محاسبه کند. برای بهتر متوجه شدن خواستهی سوال، توضیحات نمونهها را مطالعه کنید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(t\) آمده که تعداد تستها را نشان میدهد.
\[1 \leq t \leq 10 \,000\]
در سطر اول هر تست، عدد صحیح و مثبت \(n\) داده میشود که تعداد برنامهنویسها را نشان میدهد.
\[1 \leq n \leq 100\]
در یک سطر \(n\) رشته با فاصله داده میشود که رشتهی سطر \(i\)ام تخصص برنامهنویس \(i\)ام را نشان میدهد.
خروجی
در تنها سطر خروجی، یک عدد صحیح برابر بیشترین تعداد تیم کامل را چاپ کنید.
مثالها
ورودی نمونه ۱
3
5
B F P BFP BF
4
BF BP FP B
2
B BFP
خروجی نمونه ۱
2
2
1
در نمونهی اول تیمبندی میتواند به صورت زیر باشد: \[\{B, F, P\},\quad \{BFP\}\]
در نمونهی دوم تیمبندی میتواند به صورت زیر باشد: \[\{B, FP\}, \quad \{BF, BP\}\]
در نمونهی سوم تیمبندی میتواند به صورت زیر باشد: \[\{BFP\}\]