Cho \(N\) công việc. Mỗi công việc được biểu diễn như một bộ \(3\) số nguyên dương \(<JobId, Deadline, Profit>\), trong đó \(JobId\) là mã của việc, \(Deadline\) là thời gian kết thúc của việc, \(Profit\) là lợi nhuận đem lại nếu hoàn thành việc đó đúng thời gian. Thời gian để hoàn thành mỗi công việc là \(1\) đơn vị thời gian. Hãy cho biết lợi nhuận lớn nhất có thể thực hiện các việc với giả thiết mỗi việc được thực hiện đơn lẻ.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai phần:
  • Phần thứ nhất là số lượng Job \(N\ (1 \le N \le 1000)\);
  • Phần thứ hai đưa vào \(3 \times N\) số tương ứng với \(N\) job.
  • Mỗi dòng gồm có \(<JobId, Deadline, Profit>\) (\(1 \leq JobId, Deadline, Profit \leq 1000\)).

Output

• Đưa số lượng công việc tương ứng và lợi nhuận lớn nhất có thể đạt được.

Example

2
4
1 4 20
2 1 10
3 1 40
4 1 30
5
1 2 100
2 1 19
3 2 27
4 1 25
5 1 15

2 60
2 127