In recent times, board games have surged in popularity, bringing both classic and innovative games back into the spotlight. You've discovered a brand-new, unique board game that requires a die (its net is depicted in the image) and a rectangular game board divided into cells, each containing an integer.

The game can be played by several players following these rules:
Initially, the player places the die on any face in the top-left cell of the board.
For each subsequent move, the player rolls the die onto one of the adjacent faces, moving to the cell directly to the right or below.
With each move, the player earns K \cdot A points, where is the number in the current cell, and is the number on the die face that lands on the board.
The player continues moving until reaching the bottom-right cell of the board, at which point all points from their moves are totaled.
After one player completes their moves, the next player begins, and so forth.
The player with the highest score wins the game.
Your task is to determine the maximum sum of points that can be achieved on the given game board by playing optimally according to these rules.
The first line of the input contains - the number of test cases (T \leq 200). Each test case starts with a line containing the numbers and , separated by a space, representing the dimensions of the game board (1 \leq N \cdot M \leq 10^5). This is followed by lines, each containing integers separated by spaces, representing the numbers in the board's cells. All numbers do not exceed 10^3 in absolute value.
For each test case, output a single integer on a separate line, representing the maximum number of points that can be obtained with optimal play.
Example 1