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

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

Input 

The first line of input is an integer C (C200) 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.

Output 

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.

Sample Input 

3
01??00
001010
01
10
110001
000000

Sample Output 

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

操作有三:
1. 將 0 轉換成 1
2. 將 ? 轉換成 0 或 1
3. 任意對調兩個位置上的字元

給起始字串，求轉換到目標字串的最少次數。

題目解法：

由於可以任意對調兩個位置上的字元，因此可以猜測出是一道 greedy。

操作中不存在將 1 轉換成 0，因此只要保證 0 + ? 的個數可以大於等於目標字串的 0 的個數。

肯定存在解。

1. 先 greedy 操作 2，盡可能放置與目標字串相同的字元。
2. 再 greedy 操作 1，盡可能將 0 轉換成 1 後與目標字串相同。
3. 此時已經確保目標與起始字串的 0 和 1 個數相同了，接著檢查位置不同的個數，個數/2 即操作 3 的次數。

#include <stdio.h> 
#include <string.h> 

int main() {
	int testcase, cases = 0;
	int i, j, k;
	char S[105], T[105];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%s %s", &S, &T);
		printf("Case %d: ", ++cases);
		int tone = 0, tzero = 0;
		int sone = 0, szero = 0, snone = 0;
		int serr = 0, step = 0;
		for(i = 0; T[i]; i++) {
			if(T[i] == '0')	tzero++;
			else			tone++;
		}
		for(i = 0; S[i]; i++) {
			if(S[i] == '0')
				szero++;
			else if(S[i] == '1') 
				sone++;
			else
				snone++;
		}
		if(szero+snone < tzero) {
			puts("-1");
			continue;
		}
		for(i = 0; S[i]; i++) {
			if(S[i] == '?') {
				step++;
				if(T[i] == '0' && szero < tzero)
					S[i] = '0', szero++;
				else if(T[i] == '1' && sone < tone)
					S[i] = '1', sone++;
				else if(szero < tzero)
					S[i] = '0', szero++;
				else
					S[i] = '1', sone++;
			}
		}
		for(i = 0; S[i]; i++) {
			if(sone < tone && S[i] == '0' && T[i] == '1')
				sone++, szero--, step++, S[i] = '1';
		}
		for(i = 0; S[i]; i++)
			serr += S[i] != T[i];
		printf("%d\n", serr/2+step);
	} 
	return 0;
}