+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دور یک میز گرد $n$ کارمند از شرکت گلرنگ و $m$ کارمند از شرکت کوئرا ایستاده‌اند و می‌خواهند دور میز شام بنشینند. سرآشپز می‌خواهد به کارمندان کوئرا کباب کوبیده و به کارمندان گلرنگ جوجه کباب بدهد، بنابراین می‌خواهد همه‌ی کارمندان کوئرا کنار هم و همه‌ی کارمندان گلرنگ کنار هم بنشینند. مشکل اینجاست که اکنون همه‌ی این $n+m$ نفر نشسته‌اند و حالا باید جای خود را تغییر بدهند. برای تغییر جا با توجه به اینکه مبل‌های راحتی در نظر گرفته شده، می‌توانیم یک کارمند را از دور میز بلند کنیم و در جایی دیگر بین دو کارمند اضافه کنیم. این کار یک واحد انرژی جمع را کم می‌کند. سوال اینجاست کمترین میزان انرژی که لازم داریم تا همه‌ی کارمندهای گلرنگ و کوئرا کنار هم باشند چقدر است؟ # ورودی در سطر اول ورودی،‌ عدد صحیح و مثبت $t$ آمده که تعداد تست‌ها را نشان می‌دهد. $$1 \leq t \leq 100,000$$ در سطر اول هر تست، دو عدد صحیح و مثبت $n$ و $m$ داده می‌شود که تعداد کارمندان گلرنگ و کوئرا را نشان می‌دهد. $$1 \leq n+m \leq 1,000,000$$ در سطر دوم هر تست، یک رشته به طول $n + m$ از کاراکترهای `G` و `Q` آمده است که وضعیت نشستن کارمندان را نشان می‌دهد. تضمین می‌شود که مجموع $n + m$ برای همه‌ی $t$ تست حداکثر $2,000,000$ باشد. # خروجی برای هر تست، در یک خط به ترتیب کمترین میزان انرژی لازم برای درست کردن ترتیب را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 2 2 3 GQGQQ 4 1 GGGQG ```` ## خروجی نمونه ۱ ``` 1 0 ```` ## ورودی نمونه ۲ ``` 2 1 0 G 0 1 Q ```` ## خروجی نمونه ۲ ``` 0 0 ````