F. Minimum Hamming Distancetime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou 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.InputEach 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^8OutputFor each test case, print the minimum Hamming distance between t and any good string g.ExampleInput
330000004000011116111111000100Output
0
2
1
NoteIn 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.
330000004000011116111111000100
0 2 1 
['dp', '*3500']