Có \(N\) yêu cầu thuê phòng họp, mỗi yêu cầu \((S,E,W)\) tương ứng với bắt đầu ở giờ \(S\) và kết thúc sau giờ \(E\) với chi phí trả là \(W\). Bạn có 2 phòng họp để cho thuê.

Yêu cầu: Hãy tìm cách cho thuê với lợi nhuận cao nhất.

Ví dụ, Khi bạn nhận được hai yêu cầu \((1,3,4)\) và \((3,5,2)\) thì bạn không thể cho hai yêu cầu này thuê cùng một phòng vì có trùng thời gian sử dụng là thời điểm 3. Tất nhiên, ta có thể sử dụng 2 phòng cho 2 yêu cầu này.

Input

• Dòng đầu chứa số \(T\), là số lượng test, sau đó là \(T\) nhóm dòng:

• Dòng thứ nhất là số\( N (1≤N≤3000)\).

• N dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(S,E,P (1≤S≤E≤10^9,1≤P≤10^9)\).

Output

• Với mỗi test in ra trên một dòng theo định dạng \(#k C\) với \(C\) là lợi nhuận lớn nhất thu được tương ứng với test thứ \(k\).

Sample Input

2
3
1 3 4
3 5 2
1 2 3
5
1 10 10
1 4 4
5 6 2
7 10 5
8 9 7

Sample Output

#1 9
#2 23