시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB122403535.354%

## 문제

You are given two non­empty strings S and T of equal lengths. S contains the characters ‘0’, ‘1’ and ‘?’, whereas T contains ‘0’ and ‘1’ only. Your task is to convert S into T in minimum number of moves. In each move, you can do one of these changes:

1. change a ‘0’in S to ‘1’
2. change a ‘?’ in S to ‘0’ or ‘1’
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.

## 입력

The first line of 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 ‘?’. The second line is the string T consisting of ‘0’ and ‘1’. The lengths of the strings won’t be larger than 100.

## 출력

For each case, output the case number first followed by the minimum number of moves required to convert S into T. If the transition is impossible, output −1 instead. Check the output example for the exact format.

## 예제 입력 1

3
01??00
001010
01
10
110001
000000


## 예제 출력 1

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