给你一个二进制字符串$$$^\dagger$$$ $$$s$$$,长度为$$$n$$$。
如果对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),存在索引 $$$l$$$ 和 $$$r$$$ ,则相同长度 $$$n$$$ 的二进制字符串 $$$p$$$ 被称为良好,这样:
- $$$1 \leq l \leq i \leq r \leq n$$$
- $$$s_i$$$ 是字符串 $$$p_lp_{l+1}\ldots p_r$$$ 的模式$$$^\ddagger$$$
给你另一个长度为 $$$n$$$ 的二进制字符串 $$$t$$$。求 $$$t$$$ 和任何好的字符串 $$$g$$$ 之间的最小汉明距离 $$$^\S$$$。
$$$^\dagger$$$ 二进制字符串是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。
$$$^\ddagger$$$ 字符 $$$c$$$ 是长度为 $$$m$$$ 的字符串 $$$p$$$ 的众数,如果 $$$c$$$ 在 $$$p$$$ 中出现的次数至少为 $$$\lceil \frac{m}{2} \rceil$$$。例如,$$$\mathtt{0}$$$ 是 $$$\mathtt{010}$$$ 的众数,$$$\mathtt{1}$$$ 不是 $$$\mathtt{010}$$$ 的众数,而 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 都是 $$$\mathtt{1}$$$ 的众数$$$\mathtt{011010}$$$。
$$$^\S$$$ 长度为 $$$m$$$ 的字符串 $$$a$$$ 和 $$$b$$$ 的汉明距离是满足 $$$1 \leq i \leq m$$$ 和 $$$a_i \neq b_i$$$ 的索引 $$$i$$$ 的数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 二进制字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个二进制字符串 $$$s$$$,长度为 $$$n$$$,由字符 0 和 1 组成。
每个测试用例的第三行包含一个二进制字符串 $$$t$$$,长度为 $$$n$$$,由字符 0 和 1 组成。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$,并额外保证所有测试用例的$$$n^2$$$总和不超过$$$10^8$$$
输出
对于每个测试用例,打印 $$$t$$$ 和任何好的字符串 $$$g$$$ 之间的最小汉明距离。
示例
输入 #1
3 3 000 000 4 0000 1111 6 111111 000100
输出 #1
0 2 1
注意
在第一个测试用例中,$$$g=\mathtt{000}$$$ 是一个很好的字符串,其与 $$$t$$$ 的汉明距离为 $$$0$$$。
在第二个测试用例中,$$$g=\mathtt{0011}$$$ 是一个很好的字符串,与 $$$t$$$ 的汉明距离为 $$$2$$$。可以证明,从$$$t$$$开始,不存在汉明距离小于$$$2$$$的好字符串。
在第三个测试用例中,$$$g=\mathtt{001100}$$$ 是一个很好的字符串,与 $$$t$$$ 的汉明距离为 $$$1$$$。