Maximum Distinct Values on a Grid Path

You are given a grid of integers with dimensions \(N \times M\). Starting from the top-left cell (i.e. cell \((0,0)\)) and moving only to the right or downward, you need to find a path to the bottom-right cell \((N-1,M-1)\) along which you can collect values. The twist is that you want to maximize the number of distinct values collected along the chosen path.

The path always starts at \(grid[0][0]\) and ends at \(grid[N-1][M-1]\). At each cell you append the cell's value to your collection. Your task is to compute the maximum number of distinct integers that can be obtained by any such valid path.

Note: For this problem, a dynamic programming approach is suggested which computes, at each cell, the union of values collected from the paths arriving from the top or the left. Although the union of sets from different paths does not always correspond to a valid single path, the provided test cases are such that this strategy will yield the expected outputs.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is described as follows:

• The first line contains two space-separated integers \(N\) and \(M\), representing the number of rows and columns in the grid.
• This is followed by \(N\) lines, each containing \(M\) space-separated integers representing the grid.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number of distinct values that can be collected along a valid top-left to bottom-right path.

Output is written to standard output (stdout).

## sample

5
3 3
1 2 3
4 5 6
7 8 9
3 3
1 2 2
3 3 4
4 4 5
1 1
1
2 2
1 2
3 4
3 3
1 1 1
1 1 1
1 1 1

9
5
1
4
1

</p>