Surely you've heard about the Enchanted Forest. Haven't you? At least from the fairy tales? Although nobody exactly knows where it lies, there are many tales proving its existence. For example people say that nobody who once enters the forest ever finds his way back. Anyhow, it is known that the forest is a perfect rectangle. If we divide it into unit squares, exactly one tree grows in each of the squares. And if you find the time to listen to the oldest people in the villages, they will tell you many even more curious things about the forest.
But how did it all begin?
The forest was originally called just the Forest.
Far and away there were no other forests,
so as you can see the name was in place. But on one day... It was a nice and sunny spring day,
all inhabitants of the forest were happy. But then a roar of the bear announced that the
great forest council is about to happen. All the animals left their work immediately and
hurried to the council. The hedgehog Henry
was the slowest one. Birds were singing impatiently, flies were flitting
here and there (and back again), the venison was giving off some strange noises,
the old fox was cunningly watching everything around her and the big black beer
bear got hungry once again and started to feed on the strawberries. Nobody knew
what was going on. Nobody but Olivia, the wise owl.
- My dearest friends! I'm sure everyone agrees that our forest is not very pleasing
to the eye of a visitor. There are too many kinds of trees in our forest. To be more
exact, two kinds. Elms and pines. We should get rid of one of them. Which one do you
suggest?
- Who cares... mumbled the big black bear and ate another strawberry. Most of the
other animals were confused and didn't get the point yet.
- OK, but now my second question follows. How will we get rid of them? continued Olivia.
In that very moment a wizard appeared in a flash of light. (So far he was hidden behind a tree.) His name was Genzibabel. In fact, this whole business with the trees was his idea -- he wanted to practice a new spell he just learned. He started to speak to the animals:
- I can change all the trees in your forest to one kind. I am able to cast a so-called Floodfill-Altertree spell. The only thing I have to do is to choose one of the trees. Then I'll cast the spell. In that very moment the spell is applied recursively on each of neighbor trees of the same kind and the current tree changes to the other kind (e.g. an elm turns to a pine and a pine turns to an elm). This way I can change the kind of a whole connected area consisting of one kind of trees with a single spell. However casting this spell is very exhausting. Therefore I'd like to cast it only as few times as necessary.
Remember that we can imagine the forest as a rectangle consisting of trees. Two trees are neighbors if and only if their unit squares share a common side. Your task will be the same as the magician and the animals had to solve. You have to find the minimal number of times the spell has to be cast to change all the trees in the forest to one kind. Also you have to find one way how to change the whole forest using that many spells.
On the first line of the input file there is a positive integer B -- the number of test cases. B blocks of data follow. Each block begins with two positive integers R, C -- the width and length of the rectangle. A matrix with R rows and C columns follows, describing the forest. Both rows and columns are numbered starting with 1. Value 1 in the i-th row and j-th column represents an elm, value 0 represents a pine. Each row of the matrix is on one line of the input file, between its elements there are no whitespaces.
For each block in the input file, output one line containing the minimum number T of trees that have to be enchanted. Then output T lines describing one possible solution. If there are more possible solutions, you may describe any of them. For each enchanted tree output one line with its position, first the row, then the column. Note that the order in which you enchant the trees does matter. Output the trees precisely in the order in which they have to be enchanted.
2 1 10 1011001101 9 9 001111100 010000010 100101001 100101001 100000001 101000101 100111001 010000010 001111100Output file
3 1 2 1 9 1 5 2 2 3 3 1
It wasn't the only strange thing that ever happened. Many other curious things have happened since then. The black bear changed his taste and started to feed on unsuspecting tourists. Next year there was a war between squirrels and woodpeckers. But that's already a different story...