C2. Cool Construction (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of this problem. The only difference is that in this version you need to construct any matrix with the least sum of elements.

You are given an integer $$$n$$$. You need to construct an $$$n \times n$$$ matrix $$$a$$$ that satisfies all of the following conditions :

  • $$$1 \le a_{i,j} \le 1000$$$ for all $$$1 \le i,j \le n$$$.
  • $$$\gcd(a_{i,j}$$$ $$$,$$$ $$$i+j) \gt 1$$$ for all $$$1 \le i,j \le n$$$, here $$$\gcd$$$ means greatest common divisor.
  • The bitwise XOR of all numbers of the matrix $$$a$$$ equals $$$0$$$.

In addition, there is another condition: the matrix should have the least sum of elements.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ $$$(2 \le n \le 500)$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$500$$$.

Output

For each testcase, print an $$$n \times n$$$ matrix $$$a$$$ that satisfies all the given conditions.

If there are multiple answers, print any one of them that has the least sum of elements.

It can be proved that atleast one such matrix exists under the given constraints.

Example
Input
1
2
Output
2 3 
3 2