Minimum Sum in Matrix Problem Statement

You are given a 2D matrix 'ARR' of size 'N x 3' with integers, where 'N' is the number of rows. Your task is to compute the smallest sum achievable by selecting one element from each row, following certain constraints.

The constraints for selecting elements are:

1. Once an element is chosen from a row, you cannot choose the element directly beneath it in the next row. 2. Selection of elements should avoid positions directly below previously selected elements.

Input:

The first line contains a single integer ‘T’, indicating the number of test cases. For each test case, the first line includes a single integer 'N', representing the number of rows. Each of the subsequent 'N' lines contains three integers describing the elements of each row.

Output:

For each test case, return the smallest sum possible according to the specified rules. Print the result for each test case on a new line.

Example:

Input:

T = 1
N = 3
ARR = [[1, 2, 3], [4, 8, 6], [1, 5, 3]]

Output:

8

Explanation:

The optimal selection could be: select element '1' from the first row, '6' from the second row not directly under '1', and '1' from the third row, resulting in a sum of 8.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10^3
• 0 ≤ ARR[i][j] ≤ 10^3 where ARR[i][j] represents the matrix element in the j-th column of the i-th row.

Time Limit: 1 second