Masala H

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.