#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef long long int ll;

#define INF 1000000000
#define MAX 16

int grid[MAX][MAX];
int exec;
int n;
priority_queue<int, vi, greater<int> > leo;


bool oddpar(int i, int j){
    int par = 0;
    if (i > 0){
        if (grid[i-1][j]) par++;
    }
    if (i < n-1){
        if (grid[i+1][j]) par++;
    }
    if (j > 0){
        if (grid[i][j-1]) par++;
    }
    if (j < n-1){
        if (grid[i][j+1]) par++;
    }

    return (par%2);
}

int turn (int i, int j){
    int odds=0;
    if (grid[i][j]) grid[i][j] = 0;
    else grid[i][j] = 1;

    if (i > 0) if (oddpar(i-1, j)) odds++; else odds--;
    if (i < n-1) if (oddpar(i+1, j)) odds++; else odds--;
    if (j > 0) if (oddpar(i, j-1)) odds++; else odds--;
    if (j < n-1) if(oddpar(i, j+1)) odds++; else odds--;

    return odds;
}

void backtrack(int i, int j, int odds, int moves){
        if (odds == 0) {
           for (int i = 0; i<n; i++) {for (int j = 0; j<n; j++) printf("%d ", grid[i][j]); cout<<endl; }
            leo.push(moves);
            return;
        }
        if (j == n) {backtrack(i+1, 0, odds, moves); return;}
        if (i == n) { return;}

        if (i == 0){
            backtrack(i, j+1, odds, moves); // nao mexe..
            if (grid[i][j] == 0){ // se for 0, troca e vai..
            int a = turn(i, j);
            backtrack(i, j+1, odds+a, moves+1);
            turn(i, j); // volta.
            }
        } else {

            if (oddpar(i-1, j)){
                if (grid[i][j] == 0){
                int a = turn(i,j);
                backtrack(i, j+1, odds+a, moves+1);
                    turn(i,j);
                } else {
                    return; // não dá pra fazer nada :(
                }
            } else {
                backtrack(i, j+1, odds, moves);
            }


        }
    }

int main(){

    int t; scanf("%d", &t);
    exec=0;
    while (t--){
        exec++;
        while (!leo.empty()) leo.pop();
        scanf("%d", &n);
        for (int i = 0; i<n; i++){
            for (int j = 0; j<n; j++) scanf("%d", &grid[i][j]);
        }

        int odds = 0;
        for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) odds += oddpar(i,j);

        printf("Case %d: ", exec);
        if (odds > 0) {backtrack(0, 0, odds, 0);
            if (leo.empty()) { cout << "-1" << endl; } else cout << leo.top() << endl;
        } else cout << "0" << endl;

    }
    return 0;
}