This is the hard version of the problem. The differences between two versions are the constraint of $n$ and $m$.

Vistar loves to play Minecraft.

Minecraft takes place in a three-dimensional grid world, each occupied by a specific type of cube. It focuses on allowing players to explore, interact with, and change the infinite world. And one of Vistar's favorite gameplay styles is creating buildings.

Recently, he was working on a renovation of his castle. There is an $n \times m$ sized wall in the castle, and to make it artistic, he wants to fill this wall with L-shaped concrete cubes. For example, a $2 \times 4$ example is shown below:

However, Vistar soon realizes that some walls cannot be completely tessellated(i.e., tightly paved) with an L-shape. He wishes to know that, given $n$ and $m$, what is the maximum number of L-shapes that the wall can be filled with?

Since Vistar doesn't want his castle to be too odd, he prefers at least one of $n$ and $m$ to be an even number.

The first line contains a single integer $t$ $(1\le t \le10^4)$ --- the number of test cases.

The first and only line of each test case contains two integers $n$ and $m$ $(1 \le n, m \le 2\cdot 10^5,$ at least one of $n$ and $m$ is even$)$.

It is guaranteed that the sum of $n \times m$ over all test cases does not exceed $2\cdot 10^5$.

For each test case:

Output an $n \times m$ rectangle of non-negative integers to represent your solution. For each positive integer value, it should exactly form an L-shape. For example, the following output:

is invalid, because the number 1 appears in two L-shapes and the number 3 doesn't form an L-shape.