311168: CF1943F. Minimum Hamming Distance

F. Minimum Hamming Distancetime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a binary string$^\dagger$ $s$ of length $n$.

A binary string $p$ of the same length $n$ is called good if for every $i$ ($1 \leq i \leq n$), there exist indices $l$ and $r$ such that:

• $1 \leq l \leq i \leq r \leq n$
• $s_i$ is a mode$^\ddagger$ of the string $p_lp_{l+1}\ldots p_r$

You are given another binary string $t$ of length $n$. Find the minimum Hamming distance$^\S$ between $t$ and any good string $g$.

$^\dagger$ A binary string is a string that only consists of characters $\mathtt{0}$ and $\mathtt{1}$.

$^\ddagger$ Character $c$ is a mode of string $p$ of length $m$ if the number of occurrences of $c$ in $p$ is at least $\lceil \frac{m}{2} \rceil$. For example, $\mathtt{0}$ is a mode of $\mathtt{010}$, $\mathtt{1}$ is not a mode of $\mathtt{010}$, and both $\mathtt{0}$ and $\mathtt{1}$ are modes of $\mathtt{011010}$.

$^\S$ The Hamming distance of strings $a$ and $b$ of length $m$ is the number of indices $i$ such that $1 \leq i \leq m$ and $a_i \neq b_i$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^4$) — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$ consisting of characters 0 and 1.

The third line of each test case contains a binary string $t$ of length $n$ consisting of characters 0 and 1.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, with the additional assurance that the sum of $n^2$ over all test cases does not exceed $10^8$

Output

For each test case, print the minimum Hamming distance between $t$ and any good string $g$.

ExampleInput

3
3
000
000
4
0000
1111
6
111111
000100

Output

0
2
1

Note

In the first test case, $g=\mathtt{000}$ is a good string which has Hamming distance $0$ from $t$.

In the second test case, $g=\mathtt{0011}$ is a good string which has Hamming distance $2$ from $t$. It can be proven that there are no good strings with Hamming distance less than $2$ from $t$.

In the third test case, $g=\mathtt{001100}$ is a good string which has Hamming distance $1$ from $t$.

题目大意：给定一个长度为n的二进制字符串s。如果长度也为n的二进制字符串p满足：对于任意的i（1≤i≤n），都存在l和r（1≤l≤i≤r≤n），使得s_i是字符串p_lp_{l+1}…p_r的主要元素（即出现次数至少为⌈m/2⌉），则称p是一个“好”字符串。给定另一个长度为n的二进制字符串t，求t与任意“好”字符串g之间的最小汉明距离。

输入数据格式：第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。接下来每个测试用例包含三行，第一行是一个整数n（1≤n≤10^4），表示二进制字符串s的长度。第二行是一个长度为n的二进制字符串s。第三行是一个长度为n的二进制字符串t。所有测试用例的n之和不超过10^6，所有测试用例的n^2之和不超过10^8。

输出数据格式：对于每个测试用例，输出t与任意“好”字符串g之间的最小汉明距离。

注：二进制字符串是只包含字符0和1的字符串。字符c是字符串p的主要元素，如果c在p中出现的次数至少为⌈m/2⌉。汉明距离是指两个等长字符串a和b之间，对应位置上不同字符的数量。题目大意：给定一个长度为n的二进制字符串s。如果长度也为n的二进制字符串p满足：对于任意的i（1≤i≤n），都存在l和r（1≤l≤i≤r≤n），使得s_i是字符串p_lp_{l+1}…p_r的主要元素（即出现次数至少为⌈m/2⌉），则称p是一个“好”字符串。给定另一个长度为n的二进制字符串t，求t与任意“好”字符串g之间的最小汉明距离。 输入数据格式：第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。接下来每个测试用例包含三行，第一行是一个整数n（1≤n≤10^4），表示二进制字符串s的长度。第二行是一个长度为n的二进制字符串s。第三行是一个长度为n的二进制字符串t。所有测试用例的n之和不超过10^6，所有测试用例的n^2之和不超过10^8。 输出数据格式：对于每个测试用例，输出t与任意“好”字符串g之间的最小汉明距离。 注：二进制字符串是只包含字符0和1的字符串。字符c是字符串p的主要元素，如果c在p中出现的次数至少为⌈m/2⌉。汉明距离是指两个等长字符串a和b之间，对应位置上不同字符的数量。