311013: CF1921B. Arranging Cats

B. Arranging Catstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

In order to test the hypothesis about the cats, the scientists must arrange the cats in the boxes in a specific way. Of course, they would like to test the hypothesis and publish a sensational article as quickly as possible, because they are too engrossed in the next hypothesis about the phone's battery charge.

Scientists have $n$ boxes in which cats may or may not sit. Let the current state of the boxes be denoted by the sequence $b_1, \dots, b_n$: $b_i = 1$ if there is a cat in box number $i$, and $b_i = 0$ otherwise.

Fortunately, the unlimited production of cats has already been established, so in one day, the scientists can perform one of the following operations:

• Take a new cat and place it in a box (for some $i$ such that $b_i = 0$, assign $b_i = 1$).
• Remove a cat from a box and send it into retirement (for some $i$ such that $b_i = 1$, assign $b_i = 0$).
• Move a cat from one box to another (for some $i, j$ such that $b_i = 1, b_j = 0$, assign $b_i = 0, b_j = 1$).

It has also been found that some boxes were immediately filled with cats. Therefore, the scientists know the initial position of the cats in the boxes $s_1, \dots, s_n$ and the desired position $f_1, \dots, f_n$.

Due to the large amount of paperwork, the scientists do not have time to solve this problem. Help them for the sake of science and indicate the minimum number of days required to test the hypothesis.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by descriptions of the test cases.

Each test case consists of three lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of boxes.

The second line of each test case contains a string $s$ of $n$ characters, where the $i$-th character is '1' if there is a cat in the $i$-th box and '0' otherwise.

The third line of each test case contains a string $f$ of $n$ characters, where the $i$-th character is '1' if there should be a cat in the $i$-th box and '0' otherwise.

It is guaranteed that in a test the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer on a separate line — the minimum number of operations required to obtain the desired position from the initial position. It can be shown that a solution always exists.

ExampleInput

6
5
10010
00001
1
1
1
3
000
111
4
0101
1010
3
100
101
8
10011001
11111110

Output

2
0
3
2
1
4

Note

In the first test case, you can first move the cat from the first box to the fifth, and then remove the cat from the fourth box.

In the second test case, there is nothing to do — the only cat is already sitting in the correct box.

In the third test case of input data, it takes three days to place a cat in each box.

题目大意：科学家们为了测试关于猫的假设，需要以特定的方式将猫排列在盒子中。他们有以下三种操作可以在一天内完成：1）将一只新猫放入一个空盒子；2）从盒子中移除一只猫；3）将一只猫从一个盒子移动到另一个空盒子。给定初始状态和目标状态，求达到目标状态所需的最少天数。

输入数据格式：第一行包含一个整数t，表示测试用例的数量。接下来，每个测试用例包含三行：第一行是一个整数n，表示盒子的数量；第二行是一个长度为n的字符串s，表示初始状态，'1'表示有猫，'0'表示没有猫；第三行是一个长度为n的字符串f，表示目标状态，'1'表示应该有猫，'0'表示不应该有猫。

输出数据格式：对于每个测试用例，输出一行，包含一个整数，表示从初始状态到达目标状态所需的最少操作次数。

公式（latex格式）：
t = 10^4
n = 10^5
b_i = 1 (有猫)
b_i = 0 (无猫)
s_i, f_i = '1' 或 '0'
题目大意：科学家们为了测试关于猫的假设，需要以特定的方式将猫排列在盒子中。他们有以下三种操作可以在一天内完成：1）将一只新猫放入一个空盒子；2）从盒子中移除一只猫；3）将一只猫从一个盒子移动到另一个空盒子。给定初始状态和目标状态，求达到目标状态所需的最少天数。 输入数据格式：第一行包含一个整数t，表示测试用例的数量。接下来，每个测试用例包含三行：第一行是一个整数n，表示盒子的数量；第二行是一个长度为n的字符串s，表示初始状态，'1'表示有猫，'0'表示没有猫；第三行是一个长度为n的字符串f，表示目标状态，'1'表示应该有猫，'0'表示不应该有猫。 输出数据格式：对于每个测试用例，输出一行，包含一个整数，表示从初始状态到达目标状态所需的最少操作次数。 公式（latex格式）： t = 10^4 n = 10^5 b_i = 1 (有猫) b_i = 0 (无猫) s_i, f_i = '1' 或 '0'