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

در یک استادیوم فوتبال، $n$ نفر تماشاچی در یک ردیف قرار دارند. تماشاچیان را از چپ به راست با اعداد $1$ تا $n$ شماره گذاری می‌کنیم. در یک لحظه‌ی خاص از این افراد عکسی گرفته شده است. در این تصویر هر کدام از این افراد نشسته یا ایستاده‌اند.

به یک دنباله از افراد «موج مکزیکی» می‌گوییم اگر عدد صحیحی مثل $k$ موجود باشد به طوری که:

تعداد افراد ضریبی از $2k$ باشد.
$k$ نفر اول نشسته، $k$ نفر بعدی ایستاده، $k$ نفر بعدی نشسته، و ... باشند، یا $k$ نفر اول ایستاده، $k$ نفر بعدی نشسته، $k$ نفر بعدی ایستاده، و ... باشند.

موج مکزیکی

از شما می‌خواهیم بزرگ‌ترین زیردنباله‌ای از افراد حاضر در استادیوم را پیدا کنید که تشکیل موج مکزیکی می‌دهند. توجه کنید منظور از یک زیردنباله، در نظر گرفتن زیرمجموعه‌ای از افراد با حفظ ترتیب آن‌ها است و لزومی ندارد این افراد یک بازه‌ی متوالی باشند.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد تست‌ها را نشان می‌دهد. $1 \leq t \leq 10^5$

در سطر اول هر تست، عدد صحیح و مثبت $n$ آمده که نشان‌دهنده‌ی تعداد افراد در این تصویر است. $1 \leq n \leq 10^6$

در سطر دوم هر تست، یک رشته به طول $n$ از حروف U (ایستاده) و D (نشسته) داده می‌شود.

تضمین می‌شود $\sum n$ به ازای همه‌ی $t$ تست حداکثر $10^6$ است.

خروجی

خروجی $t$ سطر دارد، در هر سطر بیشترین طول ممکن برای یک زیر دنباله‌ی موج مکزیکی چاپ کنید.

مثال

ورودی نمونه ۱

4
5
UUUUU
6
UDUUDD
6
DDDUUU
14
DUDUDDDUUUDUDU

خروجی نمونه ۱

ارسال پاسخ برای این سؤال