- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
دور یک میز گرد \(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