Maximum Coins Collection Problem

You are given a grid of non-negative integers where each cell represents the number of coins at that position. Starting from any cell, you can move in any of the 8 possible directions: up, down, left, right, and the 4 diagonals. In a single connected path, you may collect coins from each visited cell exactly once. Your task is to determine the maximum number of coins that can be collected in a single connected path for each test case.

Formally, let the grid be represented as a matrix \(A\) of size \(N \times M\). From a cell \((i,j)\), you can move to any adjacent cell \((i+\delta_i, j+\delta_j)\) where \(\delta_i, \delta_j \in \{-1, 0, 1\}\) and \((\delta_i, \delta_j) \neq (0,0)\). Compute the maximum sum over all possible connected paths.

inputFormat

The first line of input contains a single integer \(T\), the number of test cases. Each test case is described as follows:

1. The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the grid.
2. Then follow \(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 coins that can be collected in a single connected path. Output is written to standard output (stdout).

## sample

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

45
6
5

</p>