Lights Off

Problem code: E2

All submissions for this problem are available.

Lights Off is a puzzle game consisting of an n x n grid of lights. At the beginning of the game, some of the lights are switched on. When a light is pressed, this light and the four adjacent lights are toggled, i.e., they are switched on if they were off, and switched off otherwise. The purpose of the game is to switch all the lights off.

The following figure illustrates the game:

Johnny has become addicted to playing the Lights Off game on his new iPhone. Yesterday he got stuck at a difficult level. He asked you, the talented programmer, for help. Please write a program to help Johnny solve the Lights Off game, not only for the regular 5x5 board size, but also for much larger dimensions!

Input

The first line contains t, the number of test cases (about 10). Then t test cases follow.

Each test case has the following form:

  • The first line contains n, the size of the board (3 ≤ n ≤ 30).
  • Then n lines follow, each line contains n characters '0' or '1'. The character in the ith line and jth column is '0' if the corresponding light is off and '1' if it is on.

Output

For each test case, in the first line, print k, the number of times Johny must press a light. Any valid solution in which k does not exceed 5000 is accepted.

Then k lines follow, each line containing two numbers i and j (1 ≤ i, j ≤ n), describing the position of a light to be pressed. Note that (i,j) means the light in the ith row and jth column; the rows are numbered 1 to n from top to bottom, and the columns are numbered 1 to n from left to right.

Example

Input:
1
3
000
110
010

Output:
5
1 1
2 1
2 2
3 2
3 3

Output details:
The states of the game after pressing each light are:
000       110       010       000       000       000
110 (1,1) 010 (2,1) 100 (2,2) 011 (3,2) 001 (3,3) 000
010   ->  010   ->  110   ->  100   ->  011   ->  000
Author: admin
Date Added: 5-06-2009
Time Limit: 4 - 8 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

caa0502 @ 2 Jul 2009 03:43 AM

When we say 4 adjacent cells(lights), which ones are to be considered? Because, any cell which is not on the boundary has 8 adjacent cells.

madhav_iiith @ 2 Jul 2009 05:31 AM

what should we print if we dont have a solution?

xiaowuc1 @ 2 Jul 2009 06:32 AM

@sriram: Look at the figure provided.

madhav_iiith @ 2 Jul 2009 11:39 AM

Are there any test cases where there is no solution ??

caa0502 @ 2 Jul 2009 03:29 PM

@huaiyu wu: Honestly, I do not seem to get it clearly, hence the question.
Someone please let me know ...

i0exception @ 2 Jul 2009 05:16 PM

@sriram Look at the figure
@nasini No

imrankane2005 @ 3 Jul 2009 02:21 AM

can judges please check why my solution is giving internal error though It only has simple Input/Output.
From the list of recent submissions it seems that only my submission is giving internal error.

admin 2 @ 3 Jul 2009 06:47 PM

@Imran This is being looked into. As of now, apart from that, there is no problem with the judge.

frank44 @ 3 Jul 2009 07:41 PM

@admin: I'm also experiencing an "internal error". Any update on the situation?

admin 2 @ 3 Jul 2009 07:43 PM

This is being looked into.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions