Harmonious Matrices

All submissions for this problem are available.
2. Harmonious Matrices
Call an m × n matrix of bits "harmonious" if every cell in it has an even number of 1 bits as neighbors. A cell is a neighbor of itself, and also to the cells above, below, left, and right (if they exist). So the number of neighbors of a cell is at most five, but could be less, depending on where it is. The following is an harmonious 4 × 4 square of bits:
0 1 0 0
1 1 1 0
0 0 0 1
1 1 0 1
The task is to write a program which takes as input m and n, and produces an harmonious matrix of m rows and n columns of bits. The solution should avoid the allzero matrix (if possible).
Input specification
The input will begin with a number Z ≤ 40 on a line by itself. This is followed by Z lines, each of which contains two spaceseparated positive integers m and n, each of which will be at most 40.
Output specification
For each input instance, the output will be an m × n harmonious matrix of 0s and 1s. The matrix should be nonzero if possible.
Example
Sample Input: 2 4 4 1 6 Output: 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0
Author:  pulkitj16 
Tags  pulkitj16 
Date Added:  12022013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 