D. Xor Permutation Matrix
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$x$$$ ($$$0 \le x \le n-1$$$).

Construct a matrix $$$A$$$ of size $$$n\times n$$$ satisfying all of the following conditions:

  • For every $$$1 \le i, j \le n$$$, $$$0 \le A_{i,j}\le n-1$$$;
  • Every row in $$$A$$$ forms a permutation of $$$0, 1, \ldots, n-1$$$;
  • Every column in $$$A$$$ forms a permutation of $$$0, 1, \ldots, n-1$$$;
  • For every $$$1 \le i, j\le n-1$$$, $$$$$$ A_{i,j} \oplus A_{i+1,j} \oplus A_{i,j+1} \oplus A_{i+1,j+1} = x. $$$$$$

    Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Or determine that no such matrix exists.

Input

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

The only line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$2\le n\le 2500$$$, $$$0\le x \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2500$$$.

Output

For each test case, output $$$-1$$$ if no such matrix exists. Otherwise, output any valid $$$n$$$ lines of the matrix.

If several valid matrices exist, you may output any of them.

Example
Input
5
2 0
2 1
3 0
4 1
4 0
Output
0 1
1 0
-1
-1
0 2 1 3
2 1 3 0
1 3 0 2
3 0 2 1
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
Note

In the first test case, the displayed matrix has both rows and columns equal to permutations of $$$0,1$$$, and its only adjacent $$$2\times2$$$ submatrix has XOR $$$0$$$.

The second and third test cases are impossible. In the last two test cases, every adjacent $$$2\times2$$$ submatrix has XOR, respectively, $$$1$$$ and $$$0$$$.