Background

How do you know you are not a Program?

Problem Description

For two binary strings $S$, $T$ (consisting of $0$ and $1$) of length $n$ and length $n+1$. You can perform the following types of operations:

1. Remove any bit from $T$.

2. Choose $1\le l \le r \le T$. For every $i$ satisfying $l\leq i\leq r$ and $l\equiv i \pmod 2$, let $T_i\gets 1-T_i$.

You need to find the minimum number of operations to make $T=S$.

Input Format

Each test consists of multiple test cases. The first line contains a single integer $t(1\leq t\leq 10^4)$ --- the number of sets of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n(1\leq n \leq 10^5)$ --- the length of $T$.

The second line contains a single string $S$ with size $n+1$.

The third line contains a single string $T$ with size $n$.

It is guaranteed that the sum of $n$ does not exceed $2\cdot 10^5$.

Output Format

For each test case, output a single number, containing the answer to how many operations are needed at least to make all digits the same for $S$ and $T$.

1
4
10101
1111

2

3
1
11
1
3
1010
010
7
10110110
0001111

1
1
2

Hint

For the first sample, we can do operations below:

• $1\textbf 01\textbf 01\to 11111$
• $111\underline1\to 111$

So we need $2$ operations.

Constraints

This problem uses subtasks.

• Subtask 0 (15 pts): $1\leq \sum N\leq 10$.
• Subtask 1 (35 pts): $1\leq \sum N\leq 10^3$.
• Subtask 2 (50 pts): No additional constraints.

It is guaranteed that $1\leq K\leq 1000$, $1\leq \sum N\leq 10^6$, $1\leq N\le 10^6$.