Có ~n~ căn nhà cần sơn. Căn nhà ~i~ được sơn bằng một trong 3 màu Xanh, Hồng, Vàng với mức giá 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

• Ghi trên ~T~ dòng, dòng thứ ~i~ (~i = 1 \dots T~) là chi phí tối thiểu để sơn ~n~ ngôi nhà thỏa mãn điều kiện trên.

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