402923: GYM100947 K Jpeg

In computing, JPEG is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality,and JPEG typically achieves 10:1 compression with little perceptible loss in image quality. Entropy coding is a special form of lossless data compression. It involves arranging the image components in a "zigzag" order employing run-length encoding (RLE) algorithm that groups similar frequencies together, inserting length coding zeros, and then using Huffman coding on what is left.

Now i am so busy ,so i will give you a square matrix that represents pixel intensities of the image.

Your task is simple: reconstruct the image so that the value in the i^th row and j^th column of the resulting image is the value of the (i * N + j)^th pixel visited in the zigzag sequence .

Your program will be tested on one or more test cases. The first line of the input contains a single integer T (1  ≤  T  ≤  100) the number of test cases. Followed by T test cases.

Each test case consists of N+1 lines. The first line contains an integer N (2  ≤  N  ≤  100). The next lines consists of an squared pixel matrix.

For each test case print the required transformed matrix.

1
5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

1 2 6 11 7 
3 4 8 12 16 
21 17 13 9 5 
10 14 18 22 23 
19 15 20 24 25