# Paint

Bitotsav is having a coloring contest. You are given n number of boxes arranged in a straight line. You need to paint them Red, Green and Blue.No two adjacent boxes will be painted the same color.The adjacent boxes of box i are boxes i-1 and i+1. The first and last boxes are not adjacent.

Given the prices for painting each box, you need to find the minimum total cost required to perform the work.

**Input**

The first line contains the number of test cases( 1<=T<=105 ).

For every test case the first line contains the number of boxes(n).

n lines follow.ith line contains the prices for painting the ith box R,G,B respectively separated by a blank space.

1<=n<=30

1<=R,G,B<=1000

**Output**

For every test case print the minimum total cost required to perform the work on a separate line.

**Sample Input**

```
```

4

3

1 100 100

100 1 100

100 100 1

3

1 100 100

100 100 100

1 100 100

3

26 40 83

49 60 57

13 89 99

6

30 19 5

64 77 64

15 19 97

4 71 57

90 86 84

93 32 91

**Sample Output**

```
```

3

102

96

208

Problem Setter: Rounak Tibrewal

**Languages:**C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby