Cho ~N~ khối màu, mỗi khối có dạng ~[c_1 \mid val \mid c_2]~, trong đó ~c_1, c_2~ là màu của hai đầu khối và ~val~ là giá trị của khối. Mỗi khối có thể được lật ngược, khi đó khối ~[c_1 \mid val \mid c_2]~ trở thành khối ~[c_2 \mid val \mid c_1]~.

Yêu cầu: Hãy chọn một số khối và sắp xếp chúng thành dãy liên tiếp thỏa mãn:

• Hai khối đứng cạnh nhau có hai đầu tiếp xúc phải cùng màu.

• Tổng giá trị của các khối được sử dụng là lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~T~ là số trường hợp (~1 \le T \le 5~).

• ~T~ nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng với một trường hợp có định dạng:

  • Dòng đầu tiên chứa một số nguyên ~N~ (~1 \le N \le 10^5~).

  • ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~c_1, val, c_2~ (~1 \le c_1, c_2 \le 4~; ~1 \le val \le 10^5~). Dòng thứ ~i~ mô tả khối thứ ~i~ có dạng ~[c_1 \mid val \mid c_2]~.

Các số trên cùng dòng được ghi cách nhau một dấu cách.

Output

Gồm ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng của mỗi trường hợp.

Scoring

Sample Input 1

2
4
3 15 1
1 30 4
3 10 3
2 20 1
4
3 15 1
1 30 4
3 10 3
2 20 4

Sample Output 1

55
75

Notes

• Trường hợp 1:

  • Một dãy hợp lệ đạt giá trị lớn nhất là: ~[3 \mid 10 \mid 3] \rightarrow [3 \mid 15 \mid 1] \rightarrow [1 \mid 30 \mid 4]~.

  • Tổng giá trị lớn nhất: ~10+15+30=55~.

• Trường hợp 2:

  • Lật khối ~[2 \mid 20 \mid 4]~ thành ~[4 \mid 20 \mid 2]~ và ghép thành dãy ~[3 \mid 10 \mid 3] \rightarrow [3 \mid 15 \mid 1] \rightarrow [1 \mid 30 \mid 4] \rightarrow [4 \mid 20 \mid 2]~.

  • Tổng giá trị lớn nhất: ~10+15+30+20=75~.