Minimum Sum in Matrix Problem Statement

You are given a 2D matrix ARR consisting of integers with dimensions N x 3, where N represents the number of rows.

Your task is to calculate the smallest sum possible by selecting one element from each row under the following rules:

1. After selecting an element from any row, you cannot select the element directly below it in the subsequent row.
2. You are only allowed to select elements that are not directly below the previously chosen element.

Input:

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of rows.

Each of the ‘N’ subsequent lines contains three integers representing each row's elements.

Output:

For each test case, output the smallest sum possible according to the rules.

Output each test case result on a new line.

Example:

Input:

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

Output:

12
12

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^3
• 0 <= ARR[i][j] <= 10^3

Where ARR[i][j] represents the element in the j^th column of the i^th row.

Time Limit: 1 second