{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp style\u003d\"text-align: left;\"\u003eCan a man build a staircase with tetrominoes? Maybe he can, maybe he cannot, or maybe he would be confused by what the question means. Let me make this clear. The world in which we are living is submerged in chaos -- it has no rules, no regular patterns, and even if you insist it does, you must admit that clearly it is not tidy at all. But the world of Tetris is different. The whole world can be constructed by only 7 kinds of tetrominoes. You get a piece of tetromino, rotate it, move it, then place it somewhere, and if you luckily filled an entire row,\"whew!\", that row is eliminated – and this is the only rule applied to this world. It is rather easy to construct a staircase in such a regular, tidy world -- well, maybe it is.\r\n\u003c/p\u003e\u003cp\u003eIf you still don\u0027t understand what you should do (probably you don\u0027t), follow the instructions below carefully -- we are going to examine this problem seriously from now on.\u003c/p\u003e\u003cp\u003eConsider a staircase we have been talking about with length N as a staircase-shaped grid with N rows and N columns, and for the i-th row, it has i grids in it. To clarify this, a staircase with length 4 would look like this:\u003c/p\u003e\u003cp style\u003d\"text-align: center;\"\u003e\u003cimg width\u003d\"150\" height\u003d\"150\" src\u003d\"CDN_BASE_URL/f792ed172b7f6581141d130cc5bc5c69?v\u003d1715218575\"\u003e\u003c/p\u003e\u003cp\u003eTetrominoes refers to a set of blocks originated from the game Tetris, which includes 7 kinds of blocks and each of them occupies exactly 4 grids. Figure below shows the shapes of these tetrominoes.\u003c/p\u003e\u003cp style\u003d\"text-align: center;\"\u003e\u003cimg width\u003d\"682\" height\u003d\"228\" src\u003d\"CDN_BASE_URL/8c5b6c22ea4d6f080828ce86331ec9ac?v\u003d1715218575\"\u003e\u003c/p\u003e\u003cp\u003eGiven an integer N, you should cover the staircase-shaped grid (or staircase for short) with tetrominoes. For each piece of tetromino you use, you can rotate it by 0, 90, 180 or 270 degrees, then place it somewhere aligned with grid lines in the staircase. The tetrominoes you place should not overlap with each other, or outreach the staircase. Every grid in the staircase should be covered by a tetromino. The tetrominoes you place will never be eliminated, since this is not a real Tetris game.\u003c/p\u003e\u003cp\u003eYou can use any amount of each kind of tetrominoes you want to build the staircase. However, there is one restriction: you should use as many kinds of tetrominoes as possible. That is, if there exists a solution that uses up all 7 kinds of tetrominoes, your answer which uses only 6 kinds of tetrominoes will be not acceptable.\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003eSince there might be multiple solutions for a given N, you may output any one of them. To output your solution, you should assign a block number (ranging from 0 to 2\u003csup\u003e31\u003c/sup\u003e-1) to each grid in the staircase to specify which tetromino covers this grid. Two consecutive grids (sharing a common edge) with the same block number will be considered as covered by the same tetromino. The block numbers do not need to be unique among all the tetrominoes, as long as any two tetrominoes with the same block number are not adjacent (sharing at least one common edge).\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (1 \u0026lt;\u003d T \u0026lt;\u003d 10), indicating the number of test cases.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tFor each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tOne line contains an integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 300), indicating the length of the staircase you need to build."}},{"title":"Output","value":{"format":"HTML","content":"For each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tIf the solution does not exist, output a single line containing an integer -1;\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tIf there exists several solutions, output any one of them. Output N lines (N is the length of the staircase in this test case), the i-th line contains i integers (ranging from 0 to 2^31-1) separated by spaces, indicating the block number you assigned to each grid in the i-th row."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n15\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 1\r\n2 1 3\r\n2 3 3 1\r\n2 3 1 1 1\r\n2 4 4 2 2 1\r\n1 4 4 2 1 1 1\r\n1 1 1 2 3 3 3 3\r\n2 2 2 1 1 2 2 2 4\r\n2 1 3 2 1 2 3 3 4 4\r\n1 1 3 2 1 4 3 3 4 3 3\r\n1 3 3 2 3 4 4 1 1 1 3 3\r\n4 4 4 2 3 3 4 1 3 3 2 2 1\r\n3 4 1 1 3 2 2 2 3 3 2 1 1 4\r\n3 3 3 1 1 2 1 1 1 1 2 1 4 4 4\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"In the first test case, the length of the staircase is 15. The solution uses up all 7 kinds of tetrominoes. Note that you can use as many block numbers as you want while the sample output only uses four block numbers."}}]}