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

---

دور یک میز گرد \(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