Người ngoài hành tinh từ vũ trụ (cuối cùng cũng!) xâm lược Trái Đất. Hãy tự vệ, nếu không bạn sẽ bị phân rã! Hoặc bị đồng hóa. Hoặc bị ăn thịt. Chúng ta vẫn chưa chắc.

Người ngoài hành tinh tấn công theo một quy luật đã biết. Có $n$ kẻ tấn công, kẻ thứ $i$ xuất hiện vào thời điểm $a_i$, cách bạn một khoảng $d_i$. Phải tiêu diệt hắn muộn nhất vào thời điểm $b_i$, nếu không hắn sẽ khai hỏa, và điều đó chắc chắn sẽ kết thúc cuộc chiến.

Vũ khí của bạn là một khẩu pháo tấn công diện rộng, có thể đặt ở bất kỳ mức uy lực nào. Khi bắn với uy lực $R$, nó lập tức tiêu diệt tất cả người ngoài hành tinh cách bạn không quá $R$. Nó cũng tiêu tốn $R$ pin nhiên liệu.

Hãy xác định chi phí nhỏ nhất (tính bằng số pin nhiên liệu) để tiêu diệt tất cả người ngoài hành tinh mà không bị giết.

Kích thước tệp đầu vào không vượt quá 0.1 MiB.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ kiểm thử $T$. Tiếp theo là mô tả các bộ kiểm thử:

Mỗi bộ kiểm thử bắt đầu bằng một dòng chứa số người ngoài hành tinh $n$ ($1 \le n \le 300$). Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). Người ngoài hành tinh thứ $i$ xuất hiện vào thời điểm $a_i$, không hành động cho đến $b_i$, và cách bạn một khoảng $d_i$.

Dữ liệu ra

Với mỗi bộ kiểm thử, in một dòng chứa số pin ít nhất cần để tiêu diệt tất cả người ngoài hành tinh.

Ví dụ

Dữ liệu vào 1

1
3
1 4 4
4 7 5
3 4 7

Dữ liệu ra 1

7