Masala #0701
GAME
Azimjon va Azizbek ko'p birgalikda o'yin o'ynashadi. Ular har doim bir xil o'yin o'ynashdan zerikkanlari bois Politsiyachi va Qochoq o'yinini o'ynamoqchi bo'lishdi. Siz ularga yordam bering. Ular NxN jadvalda P va Q harflarini joylashtirib chiqadi bunda P-politsiyachi degani Q-Qochoq degani
- jadvaldagi har bir katakchada P yoki Q harfi bor.
- Politsiyachi o'g'rini qo'lga olishi uchun o'g'ri ham politsiyachi ham bitta qatorda bo'lishi shart va bitta politsiyachi faqat bitta qochoqni tuta oladi.
- Politsiyachi o'zidan uzog'i bilan K masofa uzoqdagi qochoqni tuta oladi.
Siz ushbu o'yinda politsiyachi uzog'i bilan nechta qochoqni tutishi mumkinligini toping.
Manba: MyContest.uz
- Birinchi qatorda \(t(0 < t < 101)\) testlar soni.
- Ikkinchi qatorda \(N(2 < N < 1000) K(0 < K < N)\) sonlari o'z navbatida Jadval o'lchami va politsiyachi borishi mumkin bo'lgan masofa.
- Keyingi N ta qator va N ta ustun da probel bilan ajratilgan 'P' va 'Q' harflari mavjud.
Har bir sinov ishi uchun jadval ichida ushlanishi mumkin bo'lgan o'g'rilarning maksimal sonini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
1 3 1 P Q P Q P Q Q Q P |
3 |