Quantum Computing este o tehnologie nouă ce folosește proprietățile mecanicii cuantice pentru a efectua anumite calcule într-un timp mult mai scurt decât este capabil să le facă un calculator clasic. Diferența fundamentală dintre un calculator clasic și unul cuantic este modul în care procesează informația. Un calculator clasic procesează informația folosind biți, care pot fi 0 sau 1. Pe de altă parte, un calculator cuantic utilizează qubiți, care pot avea în același timp și valoarea 0 (notată cu |0⟩) și valoarea 1 (notată cu |1⟩) – spunem că qubitul se află în starea cuantică |ψ⟩ = α|0⟩ + β|1⟩. Efectuând modificări asupra acestor qubiți, putem dezvolta algoritmi cuantici cu o complexitate mai bună decât a celor mai buni algoritmi clasici existenți. Totuși, calculatoarele cuantice nu au încă utilitate practică deoarece nu dispun de un număr suficient de mare de qubiți (la ora actuală cele mai puternice calculatoare cuantice au câteva sute de qubiți). Pentru simplitate, vom lucra doar cu stări pure (|0⟩ sau |1⟩).

Să considerăm un calculator cuantic cu N qubiți setați inițial la |q1⟩|q2⟩..|qN⟩. Asupra acestor qubiți se poate efectua un singur tip de operații: se inversează toți qubiții (|0⟩ devine |1⟩ și viceversa) dintr-o subsecvență (qubiți aflați pe poziții consecutive). Exemplu: |0⟩|0⟩|1⟩|0⟩ devine |0⟩|1⟩|0⟩|1⟩ dacă se inversează qubiții de pe pozițiile 2, 3 și 4. O particularitate nefericită a unui calculator cuantic este că fiecare operație introduce erori (de exemplu, este posibil ca un qubit să nu se inverseze, deși ar trebui să o facă). De aceea, este necesar ca un algoritm cuantic să efectueze un număr cât mai mic de operații.

Cerința

Aflați numărul minim de operații necesare pentru a seta toți qubiții la |1⟩ în situațiile:
1. Operațiile se pot efectua asupra subsecvențelor de orice lungime
2. Operațiile se pot efectua doar asupra subsecvențelor de lungime K

Date de intrare

Intrarea standard conține pe prima linie două numere întregi C și T, separate printr-un spațiu, unde C reprezintă tipul cerinței și T numărul de teste. Pe următoarele linii se află descrierea testelor. Dacă C = 1 atunci pe prima linie a fiecărui test se află numărul întreg N, reprezentând numărul de qubiți, iar pe a doua linie se află N caractere reprezentând starea inițială a qubiților (|0⟩ este reprezentat prin 0 și |1⟩ este reprezentat prin 1). Dacă C = 2 atunci pe prima linie a fiecărui test se află două numere întregi N și K, separate printr-un spațiu, reprezentând numărul de qubiți și lungimea unei subsecvențe pe care se poate efectua o operație, iar pe a doua linie starea inițială a qubiților, descrisă la fel ca pentru C = 1.

Date de ieșire

Ieșirea standard va conține T linii, pe fiecare linie aflându-se numărul minim de operații necesare pentru a seta toți qubiții la |1⟩. Pentru C = 1 se garantează că există mereu o soluție. Pentru C = 2, dacă nu există soluție, se va afișa −1.

Restricții și precizări

• 1 ≤ T ≤ 10
• 1 ≤ K ≤ N ≤ 1.000.000
• suma valorilor lui N pe toate testele nu va depăși 1.000.000
• Pentru 40 de puncte, C = 1
• Pentru 20 de puncte, C = 2 și N ≤ 1.000
• Pentru 40 de puncte, C = 2

Exemplul 1:

Intrare

1 2
4
0101
7
0010110

Ieșire

2
3

Explicație

Pentru primul test din primul exemplu, putem obține un număr minim de operații în următorul mod: |0⟩|1⟩|0⟩|1⟩ → |1⟩|0⟩|0⟩|1⟩ → |1⟩|1⟩|1⟩|1⟩.
Pentru al doilea test din primul exemplu, putem obține un număr minim de operații în următorul mod: |0⟩|0⟩|1⟩|0⟩|1⟩|1⟩|0⟩ → |0⟩|0⟩|1⟩|0⟩|0⟩|0⟩|1⟩ → |1⟩|1⟩|0⟩|0⟩|0⟩|0⟩|1⟩ → |1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩.

Exemplul 2:

Intrare

2 2
12 4
110100100000
5 2
01100

Ieșire

4
-1

Explicație

Pentru primul test din al doilea exemplu, putem obține un număr minim de operații în următorul mod:
|1⟩|1⟩|0⟩|1⟩|0⟩|0⟩|1⟩|0⟩|0⟩|0⟩|0⟩|0⟩ → |1⟩|1⟩|0⟩|1⟩|0⟩|0⟩|1⟩|0⟩|1⟩|1⟩|1⟩|1⟩ → |1⟩|1⟩|0⟩|0⟩|1⟩|1⟩|0⟩|0⟩|1⟩|1⟩|1⟩|1⟩ → |1⟩|1⟩|1⟩|1⟩|0⟩|0⟩|0⟩|0⟩|1⟩|1⟩|1⟩|1⟩ → |1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩|1⟩.
Pentru al doilea test din al doilea exemplu, se poate demonstra că nu există soluție.