Z Traversal

Description

Given a square matrix of size N x N. Print the Z traversal of the matrix. Refer the figure given below for better understanding.

Input

The first line of the input contains T, the number of test cases. The first line of each test case contains N, the dimension of the square matrix.

Next N lines contains N space separated integers, denoting the values of the matrix.

Constraints

1 <= T <= 10

1 <= N <= 500

1 <= A[i][j] <= 1000

Output

For each test case, print the elements that occur in the Z traversal of the matrix, on a new line.

Sample Input 1 

1
3
1 2 3
4 5 6
7 8 9

Sample Output 1

1 2 3 5 7 8 9 

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = sc.nextInt();

        //adding elements in matrix
        for (int run=0;run<times;run++){
            int size = sc.nextInt();
            // creating a matrix
            int [][]matrix = new int[size][size];

            for (int i = 0 ;i<size;i++){
                for (int j = 0;j<size;j++){
                    matrix[i][j]= sc.nextInt();
                }
            }
            if (matrix.length==1){
                System.out.print(matrix[0][0]);
            }else {
                for (int i = 0 ;i<size;i++){
                    System.out.print(matrix[0][i]+" ");
                }

                //printing the between part
                for (int i = 0 ;i<size;i++){
                    for (int j = 0;j<size;j++){
                        if(i+j==size-1 && j!=0 && j!=size-1){
                            System.out.print(matrix[i][j]+ " ");
                        }
                    }
                }

                for (int i = 0 ;i<size;i++){
                    System.out.print(matrix[size-1][i]+" ");
                }
            }
            System.out.println();
        }

    }
}