Untitled

#include<iostream>
using namespace std;

char chess[4][4];
int nTestcase, black, nr, nc, Min, cnt;
int rspin[4] = {-1,1,0,0};
int cspin[4] = {0,0,-1,1};

bool check(){
	int temp = 0;
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 4; j++){
			if(chess[i][j] == 'b') temp++;
		}
	}
	if(temp == 0 || temp == 16) return true;
	return false;
}

void backtrack(int k){
	if(cnt >= Min) return;
	if(check()){
		Min = Min > cnt ? cnt : Min;
		return;
	}
	if(k == 16) return;

	int r = k / 4;
	int c = k % 4;
	for(int i = 0; i < 2; i++){
		if(i == 0){
			//
			if(chess[r][c] == 'b'){
				chess[r][c] = 'w';
				for(int j = 0; j < 4; j++){
					nr = r + rspin[j];
					nc = c + cspin[j];
					if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
						if(chess[nr][nc] == 'b') 
							chess[nr][nc] = 'w';
						else
							chess[nr][nc] = 'b';
					}
				}
			}else{
				chess[r][c] = 'b';
				for(int j = 0; j < 4; j++){
					nr = r + rspin[j];
					nc = c + cspin[j];
					if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
						if(chess[nr][nc] == 'b') 
							chess[nr][nc] = 'w';
						else
							chess[nr][nc] = 'b';
					}
				}
			}
			//
			cnt++;
			backtrack(k + 1);
			//
			if(chess[r][c] == 'b'){
				chess[r][c] = 'w';
				for(int j = 0; j < 4; j++){
					nr = r + rspin[j];
					nc = c + cspin[j];
					if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
						if(chess[nr][nc] == 'b') 
							chess[nr][nc] = 'w';
						else
							chess[nr][nc] = 'b';
					}
				}
			}else{
				chess[r][c] = 'b';
				for(int j = 0; j < 4; j++){
					nr = r + rspin[j];
					nc = c + cspin[j];
					if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4){
						if(chess[nr][nc] == 'b') 
							chess[nr][nc] = 'w';
						else
							chess[nr][nc] = 'b';
					}
				}
			}
			//
			cnt--;
		}
		else{
			backtrack(k + 1);
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		black = 0;
		for(int i = 0; i < 4; i++){
			for(int j = 0; j < 4; j++){
				cin >> chess[i][j];
			}
		}
		if(check()){
			cout << "Case #" << testcase << endl << 0 << endl;
		}else{
			Min = 100;
			cnt = 0;
			backtrack(0);
			if(Min == 100){
				cout << "Case #" << testcase << endl << "impossible" << endl;
			}else if(Min < 100){
				cout << "Case #" << testcase << endl << Min << endl;
			}
		}
	}
	return 0;
}