Co-workers from Hell#5042

Co-workers from Hell

1 second
64 megabytes
Very easy

A watchman has to check a number of chambers in the factory each night according to a schedule that specifies the order in which the chambers must be visited and the time it takes to check each chamber. The watchman starts his job each night from the first chamber and leaves the factory and goes home when he checks the final chamber. He normally checks all other chambers, but in our story, he may not actually do so.

Having access to this schedule, a co-worker wants to have some fun one night by teasing him and making him go home very late. To do this, he can perform some tricks in a number of chambers before the watchman arrives and starts his job. Each trick in one chamber will deceive the watchman as if something may be happening in one other chamber. This makes the watchman stay a different amount of time in that chamber and continue his check in another chamber, which may be different from the chamber he normally checks afterward. When he goes to a new chamber, he continues his normal check up to the end (and thus may not check some chambers at all). For example, if there are five chambers which are checked in order in normal situations and the only trick made is in chamber which makes the watchman go and check chamber , the watchman takes this path along chambers: 1 - 2 - 4 - 5, and then goes home. We assume that a trick in one chamber is only effective the first time the watchman visits that chamber and is ineffective in future visits to that chamber. With all this information, we want to write a program to help the co-worker to plan his tricks in a way to maximize the time that the watchman stays in the factory.

Input

The first number in the input line, , is the number of test cases. The first line of each test case contains a single integer (0 \leq n \leq 100), which is the number of chambers. Following the first line, there are lines describing the chambers in order. Each line contains three integers , where is the time the watchman stays in that chamber in a normal checking, is the time he stays there if we had made a trick in that chamber, and is the next chamber he must go to if the trick is made. The starting chamber is always , and the final chamber is always .

Output

The output contains lines, each corresponding to an input test case in order. The output line contains a single integer indicating the maximum possible time in which the watchman exits the last chamber.

Examples

Example

Input
1
5
2 99 4
2 2 3
2 2 4
2 2 5
2 2 5
Output
105

Example 1

Loading
Loading