Leo is back to work. After winning the Oscar Leo has decided to choose his next movies such that he gets maximum pay. Since Leo is a dedicated actor he does only one movie at a time. He can start a new movie the same month he ends a movie.Leo's agent gives him a list of movies each having three parameters start S denoting the starting month of the movie,end E denoting the ending month of the movie and finally pay P denoting the money he will be paid for that movie.Now, Leo is confused and asks for your help to choose for him those movies that will get him the maximum pay. Help Leo as we all love him.

Input

• First line contains T the number of test cases.
• First line of each test test case contains N denoting the number of movies that Leo can sign.
• Next N lines contain three space separated integers, starting month S, ending month E and pay P in million for each movie.

Output

• Maximum pay that Leo can get for the list of movies.

Constraints and Subtasks

• 1<= T<= 10
• 1<= N<= 10^4
• 1<= S<= E<= 10^7
• 1<= P<= 100

Subtask 1: 40 points

• T <= 10
• 1 <= N <= 10^3

Subtask 2: 60 points

• original constraints.

Example

Input:
1
5
1 3 50
2 4 20
4 6 40
3 5 60
7 9 100

Output:
210

Explanation:

Leo can work in movies 1 , 4 and 5 so that his pay = 50 + 60 + 100 = 210