405589: GYM102006 B Binary Hamming

The hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. For example, the hamming distance of strings "0101" and "0011" is 2 since they differ at two positions.

You are given two binary strings of length n. You can rearrange the characters in both strings. What is the maximum possible hamming distance between the two strings you can achieve?

The first line of input contains a single integer T (1 ≤ T ≤ 512), the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100), the length of the two strings.

Each of the following two lines contains a binary string of length n, where every character in both strings is either '0' or '1'.

For each test case, output, on a single line, the maximum possible hamming distance between the two strings after rearranging them.

3
4
0101
1001
3
000
101
4
0111
0111

4
2
2

For the first test case, one possible way to achieve the maximum hamming distance is by rearranging the first string to "0110" and the second string to "1001", which results in the two strings differing in all 4 positions.

For the second test case, no matter how you rearrange the strings, the maximum hamming distance is 2.

For the third test case, a possible way to achieve the maximum distance 2 is by rearranging the strings to "0111" and "1101".