Internet Problem Solving Contest

• Easy input data set – A1
• Hard input data set – A2

You are playing a computer game in which your goal is to flood the whole world.

The world is an r × c rectangle divided into unit square cells. Currently, all cells are dry. The game has two separate phases:

• In the first phase, you can use your mouse to flood some individual cells. Whenever you click a cell, it becomes a water cell. When you’re done with clicking, you can start the second phase.
• In the second phase you just wait for the water to spread. Water spreads in steps. In each step, each dry cell that shares a side with at least two different water cells changes into a water cell.

Problem specification

You are given the dimensions of the world. Flood the entire world using as few clicks as possible.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with two positive integers r and c: the dimensions of the world. The individual cells of the world have coordinates ranging from (0, 0) to (r − 1, c − 1).

You may assume that t = 100 and that 1 ≤ r, c ≤ 100.

In the easy subproblem A1 you may also assume that r = c (i.e., the world is a square).

Output specification

For each test case output a block of lines. The first line of the block should contain the number x of clicks you should make. Each of the following x lines should contain the coordinates of a cell you should click. There are usually multiple optimal solutions. We will accept any of them.

What to submit

Do not submit any programs. Your task is to produce and submit the correct output files a1.out and a2.out for the provided input files a1.in and a2.in.

Example

Input:

2

2 2

3 4

Output:

2
0 1
1 0
4
0 0
0 2
2 2
2 3

The second sample output is illustrated below, with ‘W’ denoting a water cell and ‘.’ denoting a dry cell. On the left is the state of the world just after you made the four clicks. Progressing towards the right you see how the water spreads until it floods the entire world.

        W.W.        WWW.        WWW.        WWWW        WWWW
        ....   ->   ..W.   ->   .WWW   ->   WWWW   ->   WWWW
        ..WW        ..WW        ..WW        .WWW        WWWW