دو مورچه‌خوار جلوی یک صف از مورچه‌ها ایستاده‌اند و می‌خواهند مورچه‌ها را بخورند‎!‎ می‌دانیم هر کدام از مورچه‌ها یا مورچه‌ی کارگر هستند یا مورچه‌ی ملکه.

از طرف دیگر، هر مورچه‌خوار در هر لحظه می‌تواند یکی از انتخاب‌های زیر را برای خوردن برگزینَد:

• یک یا دو مورچه‌ی ملکه
• دو یا سه یا چهار مورچه‌ی کارگر
• «‎یک مورچه‌ی ملکه و یک مورچه‌ی کارگر‎» (ترتیب آن دو مورچه (اوّل ملکه یا اوّل کارگر) مهم نیست.)‎

البته در حالتی که تنها یک مورچه‌ی کارگر در صف مانده باشد، آن مورچه به‌تنهایی و در یک نوبت قابل خوردن است.

از آن‌جا که هضم کردن هر وعده (از بین انتخاب‌های گفته‌شده)، همانند زمان لازم برای بلعیدن، احتیاج به یک ثانیه وقت دارد، مورچه‌خوارها یکی در میان اقدام به‌خوردن مورچه‌های نوبت خودشان می‌کنند.اما چون مورچه‌خوارها خیلی بامرام هستند، هر کدام‌شان دوست دارند آخرین مورچه‌ی صف را مورچه‌خوار دیگر بخورد‎!‎

اکنون شما باید تعیین کنید که اگر هر دو مورچه‌خوار بهترین نحوه‌ی انتخاب‌شان را انجام بدهند، کدام مورچه‌خوار برنده می‌شود و مورچه‌ی آخر را نمی‌خورَد. فرض کنید که شماره‌ی مورچه‌خوارها ‎۱‎ و ‎۲‎ است و مورچه‌خوار ‎۱‎ ابتدا شروع به خوردن می‌کند. هم‌چنین هر مورچه‌خوار در نوبت خودش حتماً باید حداقل یک مورچه بخورد و مورچه باید ‎‎ الزاما‎ً به ترتیب صفشان (از ابتدای صف در سمت چپ) خورده شوند.

• در سطر اوّل ورودی، تعداد تست‌های ورودی آمده است.
• سپس هر تست در یک سطر توصیف شده است که در ابتدای آن تعداد مورچه‌ها ‎($n$)‎ آمده است و در ادامه‌ی همان سطر، ‎$n$‎ کاراکتر (با فاصله بین‌شان) مورچه‌ها را توصیف می‌کند. کاراکتر ‎$Q$‎ به‌معنی مورچه‌ی ملکه و کاراکتر ‎$W$‎ به‌معنی مورچه‌ی کارگر است.
• به جز این دو نوع کاراکتر، کاراکتر دیگری در سطر دوم تست وجود نخواهد داشت.
• دقت کنید که اوّلین (سمت چپ ترین) کاراکتر، اوّلین مورچه در صف است که باید زودتر از بقیه مورچه (الزاماً توسط مورچه‌خوار شماره‌ی ‎(۱، به‌تنهایی یا همراه با تعدادی از مورچه‌های بعدی خورده شود.
• $\le 20$‎ تعداد تست‌ها ‎$1 \le$‎ و در تمام تست‌ها ‎$1 \le n \le 10^5$‎.

برای هر یک از تست‌های ورودی در یک سطر شماره‌ی مورچه‌خواری که برنده می‌شود (‎1 یا ‎(2‎ را بنویسید.

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

• سوال بعد
• سوال قبل