Spiral Sum of Tree Heights

You are given a matrix representing the heights of trees in a field. The task is to traverse the matrix in a spiral order and compute the sum of the tree heights in that order. The spiral order can be either clockwise or counterclockwise.

For a matrix \(A\) of dimensions \(m \times n\), let the spiral order traversal produce the sequence \(a_1, a_2, \dots, a_k\). You need to compute the sum \[ S = \sum_{i=1}^{k} a_i \] and output the result for each test case.

The spiral traversal is defined as follows:

• Clockwise: Start from the top-left corner, move right, then down, then left, then up and repeat.
• Counterclockwise: Start from the top-left corner, move down, then right, then up, then left and repeat.

Read the input from stdin and output the results to stdout.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. The description of each test case is as follows:

1. The first line contains two integers \(m\) and \(n\), the number of rows and columns in the matrix.
2. The next \(m\) lines each contain \(n\) space-separated integers representing the tree heights.
3. The last line of the test case contains a string which is either "clockwise" or "counterclockwise", indicating the spiral direction.

All the input is read from stdin.

outputFormat

For each test case, output a single integer on a new line which is the sum of the tree heights obtained by performing the spiral order traversal in the specified direction. The output should be printed to stdout.

## sample

1
1 1
1
clockwise

1

</p>