Bessie は眠りたいのですが、農場の明かりのせいで眠れません。どうすれば明かりを消せるでしょうか？

Bessie は長さ $N$ の 2 つのビット列を持っています ($2\le N\le 20$)。それぞれ、明かりの列とスイッチの列を表します。各明かりは点灯（1）または消灯（0）しています。各スイッチは有効（1）または無効（0）です。

1 回の手は、次の操作をこの順序で行うことからなります。

1. ちょうど 1 つのスイッチを切り替えます（無効なら有効にし、その逆も同様です）。
2. 各有効なスイッチについて、対応する明かりの状態を切り替えます（点灯していれば消灯し、その逆も同様です）。
3. スイッチを右へ 1 つ巡回シフトします。具体的には、スイッチを表すビット列が最初に $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

注記

• 1 番目のテストケース：明かりはすでにすべて消えています。
• 2 番目のテストケース：1 手目に 3 番目のスイッチを切り替えます。
• 3 番目のテストケース：1 手目に 1 番目のスイッチ、2 手目に 2 番目のスイッチ、3 手目に再び 2 番目のスイッチを切り替えます。
• 4 番目のテストケース：1 手目に 1 番目のスイッチ、2 手目に 3 番目のスイッチを切り替えます。

どの場合も、これが必要な最小の手数であることを示せます。

入力 2

1 10
1100010000 1000011000

出力 2

2

注記

すべての明かりを消すには $2$ 手必要であることを示せます。

• 1 手目に 7 番目のスイッチを切り替え、2 手目にもう一度同じスイッチを切り替えます。

小課題

• 入力 3-5：$N \le 8$
• 入力 6-13：$N\le 18$
• 入力 14-20：追加の制約はありません。

問題作成：William Yue、Eric Yang、Benjamin Qi