Minimum Number of Swaps to Transform Binary Strings

You are given two binary strings S1 and S2 of equal length containing only characters '0' and '1'. You are allowed to perform swaps between any two positions in the string.

The task is to determine the minimum number of swaps required to transform S1 into S2 if such a transformation is possible. A necessary and sufficient condition for the transformation to be possible is that both strings have the same number of '0's and '1's; in other words, they must be permutations of each other.

If the transformation is possible, then the minimum number of swaps required is given by:

$$\max(\text{count}_{10},\;\text{count}_{01})$$

where:

• $$\text{count}_{10}$$ is the number of indices i such that S1[i]='1' and S2[i]='0',
• $$\text{count}_{01}$$ is the number of indices i such that S1[i]='0' and S2[i]='1'.

If the transformation is not possible, output -1.

inputFormat

The first line of input contains an integer T (T ≥ 1), representing the number of test cases.

Each test case consists of two lines. The first line contains the binary string S1 and the second line contains the binary string S2. Both strings have equal length.

outputFormat

For each test case, output a single integer on a new line: the minimum number of swaps required to transform S1 into S2. If it is impossible, output -1.

## sample

5
1100
1001
1010
0101
1111
1110
0101
1010
1100
0011

1
2
-1
2
2

</p>