I. Interesting Constructive
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a $$$n$$$-by-$$$m$$$ grid. Initially every cell is white, and your goal is to make all cells black.

On your first move, you can pick any cell and color it black. After that, you can only perform the following operation:

  • Choose some white cell that has exactly $$$1$$$ or $$$3$$$ black neighbors, and color it black. Here, a cell's neighbors are those cells that share a side with it. See the examples for clarification.

You need to construct a sequence of operations that colors in the grid, or report it is impossible.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^3$$$).

The only line of each test contains $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 50$$$).

Output

If the goal is impossible, output -1.

Otherwise, output $$$n\cdot m$$$ lines, each containing two integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le n$$$, $$$1 \le c \le m$$$).

This represents a sequence of operations where on the $$$i$$$-th step ($$$1 \le i \le nm$$$), you color in cell $$$(r_i, c_i)$$$. The sequence you output must be valid.

If there are multiple answers, you can output any.

We guarantee that the total size of the correct output across all tests does not exceed $$$5\cdot 10^5$$$ lines.

Example
Input
2
3 2
12 34
Output
3 2
3 1
2 1
1 1
1 2
2 2

-1
Note

In the first test, here is a picture of the operations:

In all steps except for the first and last, the cell being colored in has $$$1$$$ neighbor. In the last step, it has $$$3$$$ neighbors.

In the second test, we can show there is no answer.