Masala #0701

Xotira 2 MB Vaqt 500 ms Qiyinchiligi 30 %
14

  

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


Kiruvchi ma'lumotlar:

  • 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.

Chiquvchi ma'lumotlar:

Har bir sinov ishi uchun jadval ichida ushlanishi mumkin bo'lgan o'g'rilarning maksimal sonini chop eting.


Misollar
# input.txt output.txt
1
1
3 1
P Q P
Q P Q
Q Q P
3
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin