+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
دور یک میز گرد $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
````
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.