Minimum Cost to Paint Houses

You are given T test case(s). For each test case, you are provided an integer N representing the number of houses. Then, for each house, you are given three integers that denote the cost to paint the house in red, green, and blue respectively.

Your task is to compute the minimum total cost to paint all the houses in such a way that no two adjacent houses have the same color.

The optimization can be described by the recurrence:

\[ dp[i][c] = cost_{i,c} + \min_{c' \neq c} dp[i-1][c'] \]

where \( cost_{i,c} \) is the cost to paint the \( i^{th} \) house with color \( c \) and \( dp[i][c] \) is the minimum cost to paint up to house \( i \) with color \( c \).

• Constraints: 1 \( \leq T \leq 50 \), 1 \( \leq N \leq 1000 \), and painting cost is between 1 and 10⁴.

inputFormat

The input is read from standard input (stdin) and is organized as follows:

1. The first line contains an integer T, the number of test cases.
2. For each test case:
• The first line contains an integer N (the number of houses).
• The following N lines each contain three space-separated integers. The three numbers denote the cost to paint the current house in red, green, and blue respectively.

outputFormat

For each test case, output a single line to standard output (stdout) containing the minimum total cost to paint all the houses such that no two adjacent houses have the same color.

## sample

1
3
1 2 3
1 2 3
3 3 1

4

</p>