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

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0