- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
چه برایمان آوردهای مارکو؟ سوالی است که هر کس پس از بازگشت مارکو از سفر از او خواهد پرسید! پس مارکو سعی میکند در هر سفر بیشترین سوغات ممکن را با خود همراه داشته باشد تا شرمنده دوستان و همشهریان خود نشود.
در هر سفر مارکو, تعدادی فروشگاه در مسیر او قرار دارد که او به ترتیب آنها را میبیند. هر فروشگاه دو حق انتخاب به مارکو میدهد و او دقیقا باید یکی از آن دو را انتخاب کند. توجه کنید ممکن است هر دو حق انتخابی که به مارکو میدهند یکچیز باشد یا به عبارتی توهم آزادی انتخاب!
هر حق انتخاب یکی از این دو است:
۱. مارکو میتواند یک سوغاتی بخرد که ما آن را حق انتخاب buy_one مینامیم.
۲. مارکو میتواند تعداد سوغاتیهای خود را دو برابر کند که ما آن را copy_paste مینامیم.
حال به مارکو بگویید از هر سفر چه تعداد سوغات میتوان بیاورد.
ورودی
در سطر اول ورودی \(t\) تعداد سفرهای مارکو میآید. سپس اطلاعات \(t\) سفر در خطوط بعد میآید.
\[ 1 \le t \le 1000\]
در خط اول سفر \(i\) تعداد فروشگاهها \(S_i\) میآید سپس در \(S_i\) سطر بعد در هرکدام دو رشته با فاصله میآید که حق انتخابهای مارکو را نشان میدهد. هر حق انتخاب یکی از buy_one یا copy_paste است.
\[1 \le S_i \le 30\]
خروجی
به ترتیب برای هر سفر بیشترین سوغاتی ممکن در دست مارکو پس از سفر را در سطری جداگانه خروجی دهید.
مثال
ورودی نمونه ۱
3
1
buy_one copy_paste
3
copy_paste copy_paste
buy_one copy_paste
copy_paste copy_paste
2
buy_one buy_one
copy_paste copy_paste
خروجی نمونه ۱
1
2
2