CodeChef submission 48146 (C++ 4.0.0-8) plaintext list. Status: AC, problem E2, contest JULY09. By gmark (Mark Greve), 2009-07-04 17:41:35.
// Lights Off
// Source: CodeChef July 2009 Challenge
// CodeChef ID: E2
// Date: 04-07-2009
// Author: Mark Greve
// Keywords: linear algebra, linear equation systems, Gaussian elemination, fields, mod 2.
// Status: AC
// Difficulty: medium
// Complexity: O(n^6)
// Comments:
// We can easily model this with a linear equation system.
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
// Mod 2
template <class T> struct Field { // Arithmetic over the finite field F_{p}.
	T x; // 0 <= x < p
	Field(T a=0) { x = (a + 2)&1; }
	Field operator+(const Field& a)  { return Field(x+a.x);              }
	Field operator-(const Field& a)  { return Field(x-a.x);              }
	Field operator*(const Field& a)  { return Field(x*a.x);              }
	Field operator/(const Field& a)  { return Field(x*a.inv());          }
	Field operator-()                { return Field(-x);                 }
	bool operator>(const Field& a)   { return x> a.x;                    }
	bool operator>=(const Field& a)  { return x>=a.x;                    }
	bool operator==(const Field& a)  { return x==a.x;                    }
	bool operator!=(const Field& a)  { return x!=a.x;                    }
	friend ostream &operator<<(ostream &out, Field a) { return out << a.x; }
	T inv() const { return x; }
};
template <class T> Field<T> abs(const Field<T>& a) { return a; }
 
//////////////////////// MATRIX PART ///////////////////////////////
#define REP(i,a,b) for (int i=(a);i<(b);++i) 
template <class T> struct Row    : public vector<T> {};
template <class T> struct Matrix : public vector<Row<T> > {
		Matrix(int m, int n) { // m rows and n columns (m x n matrix)
			this->resize(m); REP(i,0,m) (*this)[i].resize(n,0);
		}
		Matrix<T> operator*(const Matrix<T>& M) const {//Matrix mult.
			int m = this->size(),n = M[0].size(),d = M.size();
			Matrix R(m,n);
			REP(i,0,m)REP(j,0,n)REP(k,0,d)R[i][j]=R[i][j]+(*this)[i][k]*M[k][j];
			return R;
		}
		Matrix<T> operator+(const Matrix<T>& M) const {
			int m = this->size(),n = (*this)[0].size();
			Matrix R(m,n);
			REP(i,0,m)REP(j,0,n)R[i][j]=(*this)[i][j]+M[i][j];
			return R;
		}
		Matrix<T> operator-(const Matrix<T>& M) const {
			int m = this->size(),n = (*this)[0].size();
			Matrix R(m,n);
			REP(i,0,m)REP(j,0,n)R[i][j]=(*this)[i][j]-M[i][j];
			return R;
		}
		Matrix<T> operator*(const T& r) const {
			int m = this->size(),n = (*this)[0].size();
			Matrix R(m,n);
			REP(i,0,m)REP(j,0,n)R[i][j]=r*(*this)[i][j];
			return R;
		}
};
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
template <class T> void show(const Matrix<T>& A) { // Helper function.
	REP(i,0,A.size()) {
		REP(j,0,A[i].size()) { cout << A[i][j] << "   ";} cout << endl;
	}
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
 
/////////////////////// GAUSSIAN ELIMINATION PART //////////////////
template <class T> T to_row_echelon_form(Matrix<T>& A){//Choose pivoting.
	// m x n matrix,converts matrix into ROW ECHELON FORM.
	T det = T(1); // Note: The matrix is considered to be augmented, ie. the n-1.
	for (int i=0,j=0,m=A.size(),n=A[0].size(); i < m && j < n-1; ++j) {
		int maxi=i; // Partial pivoting is the standard.....................
		REP(k,i+1,m)if(abs(A[k][j])>abs(A[maxi][j]))maxi=k;//Partial pivot.
		//REP(k,i+1,m)if(abs(A[k][j])!=T(0)) {maxi=k; break;}//Stupid pivot.
		if (A[maxi][j] == T(0)) { det = T(0); continue; } // not invertible.
		if (i!=maxi) swap(A[i],A[maxi]), det = -det; // Swap rows.
		REP(u,i+1,m) {
			T r = A[u][j]/A[i][j];
			if(r!=T(0)) REP(k,0,n) A[u][k] = A[u][k]-r*A[i][k];
		}
		T r = A[i][j]; det = r*det;//REP(k,0,n)A[i][k]=A[i][k]/r;//May be omitted
		++i;                       //Above ensures all diagonal elements are 1.
	}                            //In some cases stupid pivoting might be better
	return det;                  //Eg. rationals with long long or bignum.
}
template <class T> T to_reduced_row_echelon_form(Matrix<T>& A) {
	// Converts the matrix A into REDUCED ROW ECHELON form.
	// Returns the 'determinant' of the matrix.
	T det = to_row_echelon_form(A);//Note: The matrix is augmented (the n-1).
	for (int m=A.size(),n=A[0].size(),i=m-1;i>=0;--i) {
		int j=i; while (j<n-1 && A[i][j]==T(0)) ++j;
		if (j>=n-1) continue;
		T r = A[i][j];// REP(k,j,n) A[i][k] = A[i][k]/r; // Normalize (if you want).
		for (int h=i-1;h>=0;--h)
		{	r = A[h][j]/A[i][j];if(r!=T(0))REP(k,j,n)A[h][k]=A[h][k]-r*A[i][k];}
	} return det;
}
template<class T> int consistent(Matrix<T>& A) {
	int m=A.size(),n=A[0].size(); // A is the augmented matrix.
	REP(i,0,m) { // Consistent iff we have no row 0 0 0 0 | c, where c != 0.
		if (A[i][n-1]==T(0)) goto next; // This row has augmented part = 0, OK
		REP(j,0,n-1) if (A[i][j] != T(0)) goto next; // Found nonzero, so OK
		return 0; next: ;                            // Found only zeros, BAD!
	} return 1;
}
template<class T> int free_vars(Matrix<T>& A) { // A must be in row echelon form
	// Find the number of free variables in augmented matrix A.
	int m=A.size(),n=A[0].size(),vars=n-1; // n-1 is correct, since A is augmented
	REP(i,0,m) REP(j,0,n) if (A[i][j] != T(0)) { --vars; break; }
	return vars;
}
template <class T> bool solve(Matrix<T>& A, Row<T>& b, Row<T>& x) {
	// Solves Ax = b by back-substitution, A: n x n matrix, b 1 x n row vector.
	// A is changed, returns empty vector if the system is inconsistent.
	// Returns true iff system is consistent (a solution is returned in x).
	int m = A.size(), n=A[0].size();
	REP(i,0,m) A[i].push_back(b[i]);
	T det = to_row_echelon_form(A);
	if (!consistent(A)) return x=Row<T>(), 0; //inconsistent
	x.resize(n);
	for (int i=m-1;i>=0;--i) {
		int j=i; while (j<n && A[i][j]==T(0)) ++j;
		if (j>=n) continue;
		x[j] = A[i][n];
		REP(k,j+1,n) if(A[i][k]!=T(0)) x[j] = x[j]-A[i][k]*x[k];
		x[j] = x[j] / A[i][j];
	} return 1;
}
template <class T> T to_inverse(Matrix<T>& A) {
	// Finds the inverse of A, assume n=m, ie. n x n matrix.
	// Returns the determinant of A, 0 if not invertible.
	int n=A.size(); Matrix<T> C(n,2*n);
	REP(i,0,n) REP(j,0,n) C[i][j]=A[i][j];
	REP (i,0,n) C[i][i+n] = T(1);
	T det = to_reduced_row_echelon_form(C);
	if (det == T(0)) return det;
	REP(i,0,n) REP(j,0,n) A[i][j]=C[i][j+n];
	return det;
} 
// Check that x is a solution to Ax = b.
template<class T> bool check(Matrix<T>& A, Row<T>& x, Row<T>& b) {
	int m=A.size(),n=A[0].size();
	REP(i,0,m) {
		T r=T(0); REP(j,0,n) r = r + A[i][j]*x[j];
		if (b[i]!=r) return 0;
	} return 1;
}
 
char B[1000][1000];
int s[1000][1000];
int n;
 
bool in_range(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; }
 
void solve() {
	scanf("%d", &n);
	for (int i=0;i<n;++i) {
		scanf("%s", B[i]);
		for (int j=0;j<n;++j) s[i][j]=(B[i][j]=='1');
	}
 
 
	const int dx[]={-1,1,0,0,0};
	const int dy[]={0,0,-1,1,0};
 
	Matrix<Field<int> > M(n*n,n*n);
	Row<Field<int> > b; b.resize(n*n);
	for (int i=0;i<n;++i) {
		for (int j=0;j<n;++j) {
			int cur = n*i + j;
			if (s[i][j]) b[cur] = b[cur] + Field<int>(1);
			for (int k=0;k<5;++k) {
				int ni = i + dx[k];
				int nj = j + dy[k];
				if (in_range(ni,nj)) {
					int var = ni*n + nj;
					M[cur][var] = Field<int>(1);
				}
			}
		}
	}
 
	//printf("M\n"); show(M); printf("END M\n");
	//for (int i=0;i<n*n;++i) cout << b[i] << endl;
	//cout << "ENd B " << endl;
 
	Row<Field<int> > x; x.resize(n*n);
	assert(solve(M,b,x));
	int ans = 0;
	for (int i=0;i<n*n;++i) {
		//cout << x[i] << " vs " << s[i/n][i%n] << endl;
		if (x[i]==Field<int>(1)) ++ans;
	}
	//printf("ANS\n");
	printf("%d\n", ans);
	for (int i=0;i<n*n;++i) if (x[i]==Field<int>(1)) {
		printf("%d %d\n", (i/n) + 1, (i%n) + 1);
	}
}
 
int main() {
	int NCASES;
	scanf("%d", &NCASES);
	while (NCASES-- > 0) solve();
}