Matrix Median Problem Statement

You are provided with a matrix containing 'N' rows and 'M' columns filled with integers. Each row is sorted in non-decreasing order. Your task is to find the overall median of the matrix. This means if all elements of the matrix are listed in a single line, you need to determine the median of that linear array.

Input:

The first line contains a single integer 'T' representing the number of test cases.

For each test case, the first line contains two integers 'N' and 'M', denoting the number of rows and columns, respectively.

The next 'N' lines contain 'M' space-separated integers each, representing the elements in the matrix.

Output:

For each test case, print an integer which is the overall median of the given matrix.

Each test case's output should be on a separate line.

Example:

Input:

2
3 3
1 3 5
2 6 9
3 6 9
2 3
1 2 3
4 5 6

Output:

5
3

Explanation:

For the first test case, the merged sorted list of all matrix elements is [1, 2, 3, 3, 5, 6, 6, 9, 9], and the median is 5.

Constraints:

• 1 <= 'T' <= 50
• 1 <= 'N', 'M' <= 100
• 1 <= MATRIX['I']['J'] <= 105
• N * M is always an odd number.

Note:

Implementation detail: You only need to implement the required function; no need to handle input/output operations.