D. Panjara

Litsey hovlisidagi panjara bir qatorda turgan N ta taxtadan iborat. Har bir taxta oq (O), qora (Q) yoki hali bo‘yalmagan (?).

Hovli yangi ko‘rinishga ega bo‘lishi uchun oxirida barcha taxtalar bo‘yalgan va qo‘shni taxtalar har xil rangda bo‘lishi kerak.

Bo‘yalmagan taxtani bo‘yash hisobga olinmaydi — u baribir bo‘yalishi kerak edi. Lekin allaqachon bo‘yalgan taxtaning rangini almashtirish — bitta qayta bo‘yash. Eng kamida nechta taxtani qayta bo‘yash kerak?

Bir nechta panjara uchun alohida javob bering.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son T — panjaralar soni.

Keyingi T qatorning har birida O, Q va ? belgilaridan iborat bo‘sh bo‘lmagan satr — chapdan o‘ngga taxtalar.

Chiqish ma’lumotlari

Har bir panjara uchun alohida qatorda bitta butun son — qayta bo‘yaladigan taxtalarning eng kam soni.

Cheklovlar

• 1 ≤ T ≤ 10⁴
• Barcha satrlar uzunliklari yig‘indisi 2·10⁵ dan oshmaydi

1-misol, birinchi panjara OOQQ: masalan, 2- va 3-taxtani qayta bo‘yab OQOQ hosil qilamiz — 2 ta. Bittasini almashtirish yetmaydi.

Ikkinchi panjara O?O?: so‘roq belgili taxtalarni qora bo‘yaymiz — OQOQ, qayta bo‘yash kerak emas.

Uchinchi panjara QQQQQ: QOQOQ uchun 2-va 4-taxtani almashtirish yetadi — 2 ta.