O. Squaremas
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given two integers $$$m$$$ and $$$n$$$. Print a grid of integers with $$$m$$$ rows and $$$n$$$ columns such that the four corners of any rectangular subgrid add up to a perfect square. Each integer must lie in the range $$$[1, 10^9]$$$. Note that we are only interested in rectangular subgrids that have four corners. Your solution must contain at least two different numbers. It can be shown that under the given constraints, a solution always exists.

An example on a $$$3 \times 3$$$ grid is shown below. Several examples of rectangular subgrids are highlighted. The four corners of each rectangle are colored red. Note that the entire grid is also considered a subgrid.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

Each test case consists of a single line containing two integers $$$m$$$ and $$$n$$$ ($$$2 \le m, n \le 100$$$) — the required number of rows and columns of the grid.

It is guaranteed that the sum of $$$m$$$ and the sum of $$$n$$$ over all test cases are at most $$$100$$$.

Output

For each test case, output $$$m$$$ rows, each containing $$$n$$$ integers satisfying the above conditions.

If there are multiple solutions, you may output any.

Example
Input
2
2 3
3 3
Output
5 4 5
3 4 3
3 2 29
31 13 37
1 19 31
Note

The first test case is shown in the image below.

The second test case is from the image in the problem statement. There are 9 rectangles to consider. In all, we have

  • $$$3 + 2 + 31 + 13 = 49 = 7^2$$$
  • $$$2 + 29 + 13 + 37 = 81 = 9^2$$$
  • $$$31 + 13 + 1 + 19 = 64 = 8^2$$$
  • $$$13 + 37 + 19 + 31 = 100 = 10^2$$$
  • $$$3 + 29 + 31 + 37 = 100 = 10^2$$$
  • $$$31 + 37 + 1 + 31 = 100 = 10^2$$$
  • $$$3 + 2 + 1 + 19 = 25 = 5^2$$$
  • $$$2 + 29 + 19 + 31 = 81 = 9^2$$$
  • $$$3 + 29 + 1 + 31 = 64 = 8^2$$$