题目描述

给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为：

1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。
2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位置的值翻转。
3. 将 $b$ 序列向右循环移位 $1$ 位。即若当前 $b$ 序列为 $b_1b_2\cdots b_{n}$，则接下来变为 $b_{n}b_1b_2\cdots b_{n-1}$。

有 $T$ 次询问，对每一次询问，你需要回答出至少需要几次操作，才能使 $a$ 序列中每一个位置的值都变为 $0$。

输入格式

第一行为两个正整数 $T,N\;(1\leq T\leq 2\times10^5,2\leq N\leq 20)$。

接下来 $T$ 行，每行为两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$，表示一组询问。

输出格式

共 $T$ 行，每行一个正整数，表示最少的操作次数。

输入输出样例 #1

输入 #1

4 3
000 101
101 100
110 000
111 000

输出 #1

0
1
3
2

输入输出样例 #2

输入 #2

1 10
1100010000 1000011000

输出 #2

2