Consider a chessboard (a grid) of size (n \times n). You want to place as many chess pieces on this board as possible. These pieces behave in the following way: if we denote the top-left cell by ((1,1)), then a piece placed in cell ((i,j)) can attack every cell ((x,y)) such that (x \ge i) and (y \ge j), except for ((i,j)) itself. For example, on a (10 \times 10) board, a piece placed at ((3,4)) can attack the cells highlighted below: Given a chessboard with some pieces placed on it, we say that a cell is good if the number of pieces that attack that cell is even. Construct a configuration of pieces such that every cell is good, regardless of whether the cell itself contains a piece or not, and the board contains at least (\lfloor \frac{n^2}{10} \rfloor \cdot 3) pieces. 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. The first line of each test case contains an integer (n) ((1 \le n \le 5000)). It is guaranteed that the sum of (n^2) over all test cases is at most (25\,000\,000 = 5000^2). For each test case, print (n) lines. In the (i)-th line, print (n) integers separated by spaces, where a (1) represents that there is a piece in that cell, and a (0) represents that there is not. The (j)-th integer in the (i)-th line corresponds to cell ((i,j)). This example is a chessboard of dimensions (3 \times 3) where every cell is good . Cell ((3, 3)) is good because the cells with pieces ((1, 3), (2, 3), (2, 2), (3, 1)) attack it, and this count is 4, which is even. Cell ((1, 3)) is good because no piece attacks it, so the count of pieces that attack this cell is 0. Cell ((3, 2)) is good , and notice that it is required for that cell to be good even though it does not have a piece.