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.