B. Gulzor

Litsey hovlisidagi yo‘lak bo‘ylab bir qatorga N ta tuvak qo‘yilgan. Ba’zi tuvaklarda gul o‘sib turibdi, qolganlari bo‘sh. Qator N ta belgidan iborat satr bilan berilgan: # — gulli tuvak, . — bo‘sh tuvak.

Bog‘bon Dilnoza opa mehmonlar uchun chiroyli manzara yaratmoqchi: qatorda ketma-ket turgan K ta tuvakning hammasida gul bo‘lishi kerak. Buning uchun u bo‘sh tuvaklarga ko‘chat o‘tqazishi mumkin — bitta bo‘sh tuvakka bitta ko‘chat. Tuvaklarning joyini almashtirib bo‘lmaydi.

Eng kamida nechta ko‘chat o‘tqazish kerak? Bunday savol bir nechta yo‘lak uchun berilgan.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son T — yo‘laklar soni.

Har bir yo‘lak ikki qatorda beriladi: birinchisida ikkita butun son N va K, ikkinchisida N ta belgidan (# yoki .) iborat satr.

Chiqish ma’lumotlari

Har bir yo‘lak uchun alohida qatorda bitta butun son — eng kam ko‘chatlar soni.

Cheklovlar

• 1 ≤ T ≤ 10⁴
• 1 ≤ K ≤ N ≤ 2·10⁵
• Barcha yo‘laklardagi N lar yig‘indisi 2·10⁵ dan oshmaydi.

1-misol, birinchi yo‘lak: 7–10-tuvaklar #.## — bitta ko‘chat yetadi. Ketma-ket to‘rtta gulli tuvak hozircha yo‘q, shuning uchun javob 0 emas.

Ikkinchi yo‘lak: hamma tuvakda gul bor — 0. Uchinchi yo‘lak: hammasi bo‘sh — 3 ta ko‘chat kerak.