Có ~n~ căn nhà cần sơn; căn nhà thứ ~i~ được sơn bằng một trong ~3~ màu Xanh, Hồng, Vàng với chi phí sơn tương ứng là ~a_{i1}, a_{i2}, a_{i3}~.

Yêu cầu: Tìm cách sơn màu cho ~n~ ngôi nhà sao cho hai căn nhà cạnh nhau không được sơn cùng màu và tổng chi phí sơn là ít nhất.

Input

• Dòng đầu ghi số ~T~ là số test ~(T \le 100)~

• Tiếp theo là ~T~ nhóm dòng, nhóm dòng thứ ~i~ ~(i = 1, \dots, T)~ bao gồm:

  • Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 20)~ là số ngôi nhà,

  • ~n~ dòng sau, dòng thứ ~j~ ~(j = 1, \dots, n)~ chứa ba số nguyên không âm ~a_{j1}, a_{j2}, a_{j3}~ là chi phí sơn ngôi nhà ~j~ bằng các màu Xanh, Hồng, Vàng tương ứng ~(0 \le a_{jk} \le 1000)~.

Output

Gồm ~T~ dòng mỗi dòng ghi kết quả của chi phí tối thiểu để sơn ~n~ ngôi nhà thỏa mãn điều kiện trên.

Scoring

Sample Input 1

2
4
13 23 12
77 36 64
44 89 76
31 78 45
3
26 40 83
49 60 57
13 89 99

Sample Output 1

137
96

Notes

Trong test ~2~, ngôi nhà ~1~ và ~3~ sơn màu ~1~ (Xanh), ngôi nhà ~2~ sơn màu ~3~ (Vàng).