Coding Errors — Eolymp

Input

The first line contains an integer $t$ $(1 \leq t \leq 100)$ (1 \le t \le 100) — the number of test cases.

Each test case consists of three lines.

The first line of a test case contains an integer $n$ $(1 \leq n \leq 4 \cdot 1 0^{3})$ (1 \le n \le 4 \cdot 10^3) — the length of the strings $s$ and $g$ .

The second line of a test case contains the string $s$ $(0 \leq s_{i} \leq 1, ∣ s ∣ = n)$ (0 \le s_i \le 1, |s| = n).

The third line of a test case contains the string $g$ $(0 \leq g_{i} \leq 1, ∣ g ∣ = n)$ (0 \le g_i \le 1, |g| = n).

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 1 0^{3}$ 4 \cdot 10^3.

Output

For each test case, output an integer — the number of errors that occurred during transportation.

Examples

Example 1

Loading

Note

For the first test case:

The minimum transportation error can be achieved with a cyclic shift of the string $g = 01110$ g = 01110. Then the error is equal to $1$ because there exists a substring $[2, 4]$ .

Scoring

Subtask $1$ ( $25$ points): $(n \leq 10$ (n \le 10, the sum of all $n$ does not exceed $100)$
Subtask $2$ ( $50$ points): No additional constraints