Bessie vuole andare a dormire, ma le luci della fattoria la tengono sveglia. Come può spegnerle?

Bessie ha due stringhe di bit di lunghezza $N$ ($2\le N\le 20$), che rappresentano rispettivamente una sequenza di luci e una sequenza di interruttori. Ogni luce è accesa (1) oppure spenta (0). Ogni interruttore è attivo (1) oppure inattivo (0).

Una mossa consiste nella seguente sequenza di operazioni:

1. Invertire lo stato di esattamente un interruttore (renderlo attivo se è inattivo, o viceversa).
2. Per ogni interruttore attivo, invertire lo stato della luce corrispondente (spegnerla se è accesa, o viceversa).
3. Ruotare ciclicamente gli interruttori di una posizione verso destra. In particolare, se la stringa di bit degli interruttori è inizialmente $s_0s_1\dots s_{N-1}$, diventa $s_{N-1}s_0s_1\dots s_{N-2}$.

Per $T$ istanze del problema descritto ($1\le T\le 2\cdot 10^5$), calcola il numero minimo di mosse necessarie per spegnere tutte le luci.

Input

La prima riga contiene $T$ e $N$.

Ognuna delle successive $T$ righe contiene una coppia di stringhe di bit di lunghezza $N$.

Output

Per ogni coppia, stampa il numero minimo di mosse necessarie per spegnere tutte le luci.

Esempi

Input 1

4 3
000 101
101 100
110 000
111 000

Output 1

0
1
3
2

Nota

• Primo caso di test: tutte le luci sono già spente.
• Secondo caso di test: invertiamo il terzo interruttore nella prima mossa.
• Terzo caso di test: invertiamo il primo interruttore nella prima mossa, il secondo nella seconda mossa e nuovamente il secondo nella terza mossa.
• Quarto caso di test: invertiamo il primo interruttore nella prima mossa e il terzo nella seconda mossa.

Si può dimostrare che, in ciascun caso, questo è il numero minimo di mosse necessarie.

Input 2

1 10
1100010000 1000011000

Output 2

2

Nota

Si può dimostrare che sono necessarie $2$ mosse per spegnere tutte le luci.

• Invertiamo il settimo interruttore nella prima mossa e poi nuovamente nella seconda mossa.

Sottoproblemi

• Input 3-5: $N \le 8$
• Input 6-13: $N\le 18$
• Input 14-20: nessun vincolo aggiuntivo.

Autori del problema: William Yue, Eric Yang e Benjamin Qi