Bessie 想睡覺，但農場裡的燈讓她無法入睡。她怎樣才能把燈關掉呢？

Bessie 有兩個長度為 $N$ ($2\le N\le 20$) 的二進位字串，分別表示一列燈和一列開關。每盞燈要麼亮著（1），要麼熄滅（0）。每個開關要麼處於啟用狀態（1），要麼處於停用狀態（0）。

一次行動由以下依序進行的操作組成：

1. 恰好切換一個開關的狀態（如果停用，則設為啟用，反之亦然）。
2. 對於每個處於啟用狀態的開關，切換對應燈的狀態（如果燈亮著，則將它熄滅，反之亦然）。
3. 將開關向右循環移動一位。具體而言，如果表示開關的二進位字串最初為 $s_0s_1\dots s_{N-1}$，則它變為 $s_{N-1}s_0s_1\dots s_{N-2}$。

對於上述問題的 $T$ ($1\le T\le 2\cdot 10^5$) 個實例，求出將所有燈熄滅所需的最少行動次數。

輸入格式

第一行包含 $T$ 和 $N$。

接下來 $T$ 行，每行包含一對長度為 $N$ 的二進位字串。

輸出格式

對於每一對二進位字串，輸出將所有燈熄滅所需的最少行動次數。

範例

輸入格式 1

4 3
000 101
101 100
110 000
111 000

輸出格式 1

0
1
3
2

說明

• 第一組測試資料：所有燈已經熄滅。
• 第二組測試資料：我們在第一次行動中切換第三個開關。
• 第三組測試資料：我們在第一次行動中切換第一個開關，在第二次行動中切換第二個開關，在第三次行動中再次切換第二個開關。
• 第四組測試資料：我們在第一次行動中切換第一個開關，在第二次行動中切換第三個開關。

可以證明，每一組中這都是所需的最少行動次數。

輸入格式 2

1 10
1100010000 1000011000

輸出格式 2

2

說明

可以證明，將所有燈熄滅需要 $2$ 次行動。

• 我們在第一次行動中切換第七個開關，在第二次行動中再次切換它。

子任務

• 測試點 3-5：$N \le 8$
• 測試點 6-13：$N\le 18$
• 測試點 14-20：沒有額外限制。

題目作者：William Yue、Eric Yang 和 Benjamin Qi