Today is a very good day. You have just met your friend Ankur after a very long time. Ankur is a very rich person. He doesn't think twice before giving gifts to his/her friends. Today you are the lucky one!!!
He wants to give you newly built houses as gifts to you and your friends. You are given n regions denoted by their start and end points (integer points), where ith region contains pi number of houses (including the start point but excluding the end point).
At any point, the number of houses which you can get is the total number of houses of all the regions for which that point belongs to.
Since Ankur is very generous, he can give you any number of houses as you want.
Help yourself to get as much number of houses as possible.
Input:
First line of input contains t, the number of test cases. Each of the next t cases goes as follows:
First line contains n - the number of regions. Each of the next n lines contain 3 space-separated integers, where the first two integers denote the start and end point of the ith region, and the last integer denoting the number of houses pi inside that region.
Output:
Print t lines, the answer to the above problem.
Constraints:
1 <= t <= 100
1 <= n <= 10^5
1 <= pi <= 10^9
1 <= startPoint < endPoint <= 10^9
Problem Setter:
Devesh Jagwani
The point at which you can get the maximum number of houses is 5. And the maximum number of houses which you can get is 50.