paint-the-cars
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

There is a street by the name of colourful street in Cape Town. The residents of the place have decided that they will paint their cars in either Red, Black or Yellow colour and not other. They have also decided that no two adjacent cars, when kept in the houses, will have the same colour. For cars i, i-1 and i+1 are the neighbours and note that the first and the last cars are not neighbours.

The cost of painting a car in a particular colour is different. The cost of painting the first car in colour red maybe different than what its for painting the second car in the same colour.

You have to find the minimum of cost of painting the cars which satisfy the given condition.

Constraints:
1 ≤ N ≤ 20
1 ≤ cost ≤ 1000  

Input: 
The first line will contain the number of testcases, T. The second line will contain an integer N that will specify how many cars are there. Each of the following N lines will contain 3 numbers separated by space that represents the cost of painting that cars in either red, black or yellow colour respectively.

Output: 
Print T lines showing the cost of painting the cars for each testcase.

SAMPLE INPUT
1
2
11 12 13
14 15 16

SAMPLE OUTPUT
26

Explanation

The first car should be painted in Red (11), the second should be painted in Black (15). 
So the total cost becomes 11+15 = 26


def min_color_rate(num,arr):
	dp =arr
	
	for i in range(1,num):
		for j in range(3):
			dp[i][j]  = min(arr[i][j] + arr[i-1][(j+1)%3],arr[i][j] + arr[i-1][(j+2)%3])
	#print dp
	return min(dp[num-1])		



T = int(input())
for i in range(T):
	N = int(input())
	rate = []
	for j in range(N):
		rate.append(list(map(int,input().split())))
		#print rate	
	print(min_color_rate(N,rate))