Zig-Zag of Matrix

You are given a matrix ‘mat’ of ‘N’ rows and ‘M’ columns. Your task is to return the Zig-Zag order of the matrix.

The Zig-Zag order of a 5 x 5 matrix is given below

For example:

You are a given the matrix -: 
    ‘mat’ = [[1, 2, 3], 
            [4, 5, 6], 
            [7, 8, 9]]
Here the Zig-Zag order of the given matrix is [1, 2, 4, 7, 5, 3, 6, 8, 9]. Hence the answer is [1, 2, 4, 7, 5, 3, 6, 8, 9].

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of rows and columns of the matrix.

The next ‘N’ lines contain ‘M’ space-separated integers denoting the elements of the matrix ‘mat.’

Output Format:

For each test case, print N*M space-separated integers representing the Zig-Zag order of the matrix.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= N, M <= 10^3
0 <= mat[i][j] <= 10^9

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.