Bits Equalizer

You are given two nonempty strings S and T of equal length. S contains the characters “0”, “1”, and “?”, whereas T contains “0” and “1” characters only. Your task is to convert S into T in minimum number of moves. In each move, you can

1. change a “0” in S to “1”,
2. change a “?” in S to “0” or “1”, or
3. swap any two characters in S.

As an example, suppose S = “01??00” and T = “001010”. We can transform S into T in 3 moves:

• Initially S = “01??00”.
• Move 1: change S[2] to “1”. S becomes “011?00”.
• Move 2: change S[3] to “0”. S becomes “011000”.
• Move 3: swap S[1] with S[4]. S becomes “001010”.
• S is now equal to T.

Input Specification

The first line of the input is an integer C (C ≤ 200) that indicates the number of test cases. Each case consists of two lines. The first line is the string S consisting of “0”, “1”, and “?” characters. The second line is the string T consisting of “0” and “1” characters. The lengths of the strings won't be greater than 100.

Output Specification

For each test case, output the case number first as shown in the sample output, followed by the minimum number of moves required to convert S into T. If the transition is impossible, output “-1” instead.

Sample Input

1. 3
2. 01??00
3. 001010
4. 01
5. 10
6. 110001
7. 000000

download as text file

Output for Sample Input

1. Case 1: 3
2. Case 2: 1
3. Case 3: -1

download as text file