题目描述

今年，为了迎接亚运，广州的 RGB 街道的住户决定把他们的房子都刷成统一的红、绿、蓝三色之一。还规定相邻的两个房子不能刷成同样的颜色。第 $i$ 个房子相邻的是第 $i-1$ 和第 $i+1$ 房子。

现在已经知道每个房子刷成三种颜色的花费，请你计算最少要花费多少才能完成这个任务。

输入格式

多组数据，文件开始一行为 $G$ ，表示有 $G$ 组数据。下面每组数据格式为：

第 1 行：一个整数 $N$ 。

第 2 至 n+1 行： 每行三个整数 $r$ ,$g$, $b$。第 i+1 行的 $r$, $g$, $b$ 表示第 $i$ 个房子刷成红、绿、蓝色的分别花费。

数据范围

$1 \le N \le 30$ ;

$1 \le r,g,b \le 1000$;

输出格式

每组数据一行：

一个整数，完成任务的最小花费。

样例

1
3
1 100 100
100 100 100
1 100 100

102